[UESTCPC 2024] 黑白珠串

Luogu

IDLGP10330

Time1000ms

Memory256MB

DifficultyP2

2024Special JudgeO2优化高校校赛

你是宽窄巷子里的一位手艺人。这天，顾客向你订购一条黑白珠串。黑白珠串形如一条链，其上排列着黑色和白色的珠子。顾客还向你提出了 $k$ 个条件，每个条件如下： - 给定 $x,y$，要求黑白珠串中存在至少一个子串，满足子串的长度为 $x$，且恰好包含 $y$ 个黑珠。这里，子串指黑白珠串中的一段连续的珠子。请你为顾客构造出符合以上所有条件的黑白珠串，且满足珠串的长度最小。为了保证你构造的珠串满足上述条件，你还要对于每个条件，给出一个满足条件的子串的位置。 ## Input 第一行包含一个整数 $k$ $(1\leq k\leq 10^5)$，表示条件的数量。接下来 $k$ 行，其中第 $i$ 行包含两个整数 $x_i,y_i$ $(1\leq x_i\leq 10^6,0\leq y_i\leq x_i)$，表示条件的内容。 ## Output 第一行一个整数 $l$，表示满足条件的黑白珠串的最小长度。第二行一个由 ```0``` 和 ```1``` 构成的字符串，满足该字符串长度为 $l$，表示你构造的黑白珠串。其中 ```0``` 代表白珠，```1``` 代表黑珠。接下来 $k$ 行，其中第 $i$ 行包含一个整数 $p_i$，表示满足第 $i$ 个条件的一个子串在珠串中的起始位置。这里令珠串的位置编号从 $0$ 开始。 [samples]

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[UESTCPC 2024] 黑白珠串",
    "description": {
      "content": "你是宽窄巷子里的一位手艺人。这天，顾客向你订购一条黑白珠串。黑白珠串形如一条链，其上排列着黑色和白色的珠子。顾客还向你提出了 $k$ 个条件，每个条件如下： - 给定 $x,y$，要求黑白珠串中存在至少一个子串，满足子串的长度为 $x$，且恰好包含 $y$ 个黑珠。 这里，子串指黑白珠串中的一段连续的珠子。 请你为顾客构造出符合以上所有条件的黑白珠串，且满足珠串的长度最小。为了保证你构造的珠",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10330"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你是宽窄巷子里的一位手艺人。这天，顾客向你订购一条黑白珠串。黑白珠串形如一条链，其上排列着黑色和白色的珠子。顾客还向你提出了 $k$ 个条件，每个条件如下：\n\n- 给定 $x,y$，要求黑白珠串中存在至少一个子串，满足子串的长度为 $x$，且恰好包含 $y$ 个黑珠。\n\n这里，子串指黑白珠串中的一段连续的珠子。\n\n请你为顾客构造出符合以上所有条件的黑白珠串，且满足珠串的长度最小。为了保证你构造的珠...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments