QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #790148 | #6683. Difficult Constructive Problem | Nlll# | AC ✓ | 8ms | 5464kb | C++17 | 4.0kb | 2024-11-28 02:24:00 | 2024-11-28 02:24:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Maxn = 1e5 + 5;
int f[Maxn], g[Maxn], h[Maxn];
void _init(int N = 1e5)
{
for(int i = 1; i <= 1e5; i++)
{
f[i] = i / 2 * 2;
g[i] = (i + 1) / 2 * 2;
h[i] = i;
}
}
void solve()
{
int n, k;
cin >> n >> k;
string s;
cin >> s;
int pd = 0;
vector<int> len(n + 1), num(n + 1);
for(int i = n - 1; i >= 0; i--)
{
if(s[i] == '?')
{
len[i] = len[i + 1] + 1;
}
}
int now = 0, low = 0;
for(int i = n - 1; i >= 0; i--)
{
num[i] = num[i + 1];
if(s[i] == '?' && (i == 0 || len[i] > len[i - 1]))
{
if(i == 0 || i + len[i] == n) num[i] += h[len[i]];
else if(s[i - 1] != s[i + len[i]])
{
low++;
num[i] += f[len[i]];
}
else num[i] += g[len[i]];
}
if(i != n - 1 && s[i] != '?' && s[i + 1] != '?' && s[i] != s[i + 1])
{
low++;
}
//cout << i << " " << len[i] << " " << num[i] << "\n";
}
//cout << low << " !\n";
if(num[0] + low < k || low > k) s = "Impossible";
else
{
int ok = 1;
if(s[n - 1] != '?' && s[0] == '?' && len[0] != n)
{
if((k - low) % 2)
{
if(s[len[0]] == '0') s[0] = '1';
else s[0] = '0';
low++;
}
else
{
if(s[len[0]] == '0') s[0] = '0';
else s[0] = '1';
}
}
for(int i = 0; i < n; i++)
{
if(s[i] == '?')
{
int l, r;
l = low;
if(i != 0 && s[i - 1] != '0') l++;
if(i + len[i] != n && s[i + len[i]] != '0') l++;
if(i != 0 && i + len[i] != n && s[i - 1] != s[i + len[i]]) l--;
r = l + num[i + 1];
if(i + len[i] == n)
{
r += h[len[i] - 1];
}
else if(s[i + len[i]] != '0')
{
r += f[len[i] - 1];
}
else r += g[len[i] - 1];
//cout << i << " " << s << " " << l << " " << r << " " << low << "\n";
if(l <= k && k <= r)
{
s[i] = '0';
if(i != 0 && s[i - 1] != '0') low++;
if(i + len[i] != n && s[i + len[i]] != '0') low++;
if(i != 0 && i + len[i] != n && s[i - 1] != s[i + len[i]]) low--;
continue;
}
l = low;
if(i != 0 && s[i - 1] != '1') l++;
if(i + len[i] != n && s[i + len[i]] != '1') l++;
if(i != 0 && i + len[i] != n && s[i - 1] != s[i + len[i]]) l--;
r = l + num[i + 1];
if(i + len[i] == n)
{
r += h[len[i] - 1];
}
else if(s[i + len[i]] != '1')
{
r += f[len[i] - 1];
}
else r += g[len[i] - 1];
//cout << i << " " << s << " " << l << " " << r << "\n";
if(l <= k && k <= r)
{
s[i] = '1';
if(i != 0 && s[i - 1] != '1') low++;
if(i + len[i] != n && s[i + len[i]] != '1') low++;
if(i != 0 && i + len[i] != n && s[i - 1] != s[i + len[i]]) low--;
continue;
}
ok = 0;
break;
}
}
if(!ok) s = "Impossible";
}
cout << s << "\n";
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
_init();
int T;
cin >> T;
while(T--) solve();
return 0;
}
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4720kb
input:
5 9 6 1?010??01 9 5 1?010??01 9 6 100101101 9 5 100101101 9 3 ????????1
output:
100100101 Impossible 100101101 Impossible 000000101
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 8ms
memory: 5464kb
input:
6110 2 0 01 9 5 ????110?? 18 8 ???111???00??010?? 11 8 001??01???0 2 0 00 8 1 ?????111 11 2 110???01??? 13 7 ??100???01??1 6 2 ?????0 18 8 110??11??011??110? 12 5 00??011??00? 20 10 ??01???0011???0010?? 1 0 ? 13 6 ???10??110??0 6 2 00???1 17 10 ??010??001???11?? 5 2 ????0 14 7 010???00???11? 2 1 01 ...
output:
Impossible 001011001 000111000000101010 00101010010 00 00000111 11000001111 0010000101001 000010 110001100011001101 000001101001 00010000011001001010 0 0001000110010 Impossible 00010010010101100 00010 01000100010111 01 0100100001 Impossible 001100010100100101 00111111000 000 01111001 001000000100010...
result:
ok 6110 lines