QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #124928 | #6683. Difficult Constructive Problem | KKT89 | AC ✓ | 9ms | 3740kb | C++17 | 12.4kb | 2023-07-15 19:22:09 | 2023-07-15 19:22:13 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
inline double time() {
return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}
void NO() {
cout << "Impossible\n";
}
string slv_g(string s, int k) {
string res = "";
vector<int> v;
int n = s.size();
for (int i = 0; i < n; ++i) {
if (s[i] == '?') {
v.push_back(i);
}
}
n = v.size();
for (int i = 0; i < (1<<n); ++i) {
for (int j = 0; j < n; ++j) {
if ((1<<j)&i) {
s[v[j]] = '0';
}
else {
s[v[j]] = '1';
}
}
int cnt = 0;
for (int j = 0; j < (int)s.size()-1; ++j) {
if (s[j] == s[j+1]) {
cnt++;
}
}
if (cnt == k) {
if (res == "") res = s;
res = min(res, s);
}
}
if (res == "") return "Impossible";
else return res;
}
string slv(string s, int k) {
int n = s.size();
{ // 全て?の場合
bool f = true;
for (char &c : s) {
if (c != '?') {
f = false;
break;
}
}
if (f) {
for (int i = 0; i < n; ++i) {
s[i] = '0';
}
// 00000 : 4
// 00001 : 3
// 00010 : 2
// 00101 : 1
// 01010 : 0
char c = '1';
for (int i = 1+k; i < n; ++i) {
s[i] = c;
c ^= 1;
}
return s;
}
}
{
// 予め最初から連続する奴を除いておく
for (int i = 0; i+1 < n; ++i) {
if (s[i] == s[i+1] and s[i] != '?') {
k--;
}
}
}
int pre = 0; // 先頭から連続する?の個数
int bac = 0; // 末尾から連続する?の個数
// ?の開始位置、終了位置+1を持つ
vector<pair<int,int>> v;
for (int i = 0; i < n;) {
if (s[i] != '?') {
i++;
continue;
}
int j = i;
while (j < n and s[j] == '?') {
j++;
}
v.push_back({i,j});
i = j;
}
if (v.size() and v[0].first == 0) {
pre = v[0].second;
reverse(v.begin(), v.end());
v.pop_back();
reverse(v.begin(), v.end());
}
if (v.size() and v.back().second == n) {
bac = v.back().second - v.back().first;
v.pop_back();
}
int mi = 0, mx = 0;
for (auto &p : v) {
int len = p.second - p.first;
char a = s[p.first-1];
char b = s[p.second];
if (a == b) {
// 0??0
if (len % 2 == 0) {
mi += 1;
mx += len+1;
}
// 0???0
else {
mx += len+1;
}
}
else {
// 0??1
if (len % 2 == 0) {
mx += len;
}
// 0???1
else {
mi += 1;
mx += len;
}
}
}
auto check = [](int k, int mi, int mx, int pre, int bac) -> bool {
if (k < mi) return false;
if (mx+pre+bac < k) return false;
if (mi%2 != k%2 and pre == 0 and bac == 0) return false;
return true;
};
if(!check(k,mi,mx,pre,bac)) {
return "Impossible";
}
// あとは作れるはず・・・
if (pre != 0) {
if (s[pre] == '0') {
// 0000 : 4
// 0001 : 2
// 0101 : 0
// 1000 : 3
// 1001 : 1
// 000 : 3
// 001 : 1
// 101 : 2
// 00000 : 5
// 00001 : 3
// 00101 : 1
// 10000 : 4
// 10001 : 2
// 10101 : 0
auto f = [&]() -> void {
for (int i = pre; i >= 0; i -= 2) {
if (check(k-i, mi, mx, 0, bac)) {
for (int j = 0; j < pre; ++j) {
s[j] = '0';
}
int cnt = (pre-i)/2;
for (int l = 0; l < cnt; ++l) {
s[pre-1-l*2] = '1';
}
k -= i;
return;
}
}
for (int i = pre-1; i >= 0; i -= 2) {
if (check(k-i, mi, mx, 0, bac)) {
s[0] = '1';
for (int j = 1; j < pre; ++j) {
s[j] = '0';
}
int cnt = (pre-1-i)/2;
for (int l = 0; l < cnt; ++l) {
s[pre-1-l*2] = '1';
}
k -= i;
return;
}
}
};
f();
}
else {
// 0000 : 3
// 0010 : 1
// 1000 : 2
// 1010 : 0
// 1111 : 4
// 000000 : 5
// 000010 : 3
// 001010 : 1
// 100000 : 4
// 100010 : 2
// 101010 : 0
// 111111 : 6
// 00000 : 4
// 00010 : 2
// 01010 : 0
// 10000 : 3
// 10010 : 1
// 11111 : 5
auto f = [&]() -> void {
for (int i = pre-1; i >= 0; i -= 2) {
if (check(k-i, mi, mx, 0, bac)) {
for (int j = 0; j < pre; ++j) {
s[j] = '0';
}
int cnt = (pre-1-i)/2;
for (int l = 0; l < cnt; ++l) {
s[pre-2-l*2] = '1';
}
k -= i;
return;
}
}
for (int i = pre-2; i >= 0; i -= 2) {
if (check(k-i, mi, mx, 0, bac)) {
s[0] = '1';
for (int j = 1; j < pre; ++j) {
s[j] = '0';
}
int cnt = (pre-2-i)/2;
for (int l = 0; l < cnt; ++l) {
s[pre-2-l*2] = '1';
}
k -= i;
return;
}
}
assert(check(k-pre,mi,mx,0,bac));
k -= pre;
for (int i = 0; i < pre; ++i) {
s[i] = '1';
}
return;
};
f();
}
pre = 0;
}
for (auto &p : v) {
int len = p.second - p.first;
char a = s[p.first-1];
char b = s[p.second];
int cmi = 0, cmx = 0;
if (a == b) {
// 0??0
if (len % 2 == 0) {
cmi = 1;
cmx = len+1;
}
// 0???0
else {
cmx = len+1;
}
}
else {
// 0??1
if (len % 2 == 0) {
cmx = len;
}
// 0???1
else {
cmi = 1;
cmx = len;
}
}
mi -= cmi;
mx -= cmx;
if (a == '0' and b == '0') {
// 0000 : 5
// 0001 : 3
// 0101 : 1
for (int i = cmx; i >= cmi; i -= 2) {
if (check(k-i,mi,mx,pre,bac)) {
k -= i;
for (int j = p.first; j < p.second; ++j) {
s[j] = '0';
}
int cnt = (cmx-i)/2;
for (int j = 0; j < cnt; ++j) {
s[p.second-1-j*2] = '1';
}
break;
}
}
}
else if (a == '0' and b == '1') {
// 0000 : 4
// 0010 : 2
// 1010 : 0
for (int i = cmx; i >= cmi; i -= 2) {
if (check(k-i,mi,mx,pre,bac)) {
k -= i;
for (int j = p.first; j < p.second; ++j) {
s[j] = '0';
}
int cnt = (cmx-i)/2;
for (int j = 0; j < cnt; ++j) {
s[p.second-2-j*2] = '1';
}
break;
}
}
}
else if (a == '1' and b == '1') {
// 0000 : 3
// 0010 : 1
// 1111 : 5
bool done = false;
for (int i = cmx-2; i >= cmi; i -= 2) {
if (check(k-i,mi,mx,pre,bac)) {
k -= i;
for (int j = p.first; j < p.second; ++j) {
s[j] = '0';
}
int cnt = (cmx-2-i)/2;
for (int j = 0; j < cnt; ++j) {
s[p.second-2-j*2] = '1';
}
done = true;
break;
}
}
if (!done) {
assert(check(k-cmx,mi,mx,pre,bac));
k -= cmx;
for (int i = p.first; i < p.second; ++i) {
s[i] = '1';
}
}
}
else { // 1-0
// 0000 : 4
// 0001 : 2
// 0101 : 0
for (int i = cmx; i >= cmi; i -= 2) {
if (check(k-i,mi,mx,pre,bac)) {
k -= i;
for (int j = p.first; j < p.second; ++j) {
s[j] = '0';
}
int cnt = (cmx-i)/2;
for (int j = 0; j < cnt; ++j) {
s[p.second-1-j*2] = '1';
}
break;
}
}
}
}
if (bac != 0) {
if (s[n-1-bac] == '0') {
// 0000 : 4
// 0001 : 3
// 0010 : 2
// 0101 : 1
// 1010 : 0
for (int i = 0; i < bac; ++i) {
s[n-1-i] = '0';
}
char c = '1';
for (int i = n-(bac-k); i < n; ++i) {
s[i] = c;
c ^= 1;
}
}
else {
// 0000 : 3
// 0001 : 2
// 0010 : 1
// 0101 : 0
// 1111 : 4
if (k == bac) {
for (int i = 0; i < bac; ++i) {
s[n-1-i] = '1';
}
}
else {
for (int i = 0; i < bac; ++i) {
s[n-1-i] = '0';
}
char c = '1';
for (int i = n-(bac-1-k); i < n; ++i) {
s[i] = c;
c ^= 1;
}
}
}
}
// assert(k == 0);
return s;
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
// while (1) {
// int n = myRand(10)+1;
// int k = myRand(n);
// string s = "";
// for (int i = 0; i < n; ++i) {
// int u = myRand(3);
// if (u == 0) s += '0';
// else if (u == 1) s += '1';
// else s += '?';
// }
//
// if (slv(s,k) != slv_g(s,k)) {
// cout << n << endl;
// cout << s << " " << k << endl;
// cout << slv(s,k) << endl;
// cout << slv_g(s,k) << endl;
// return 0;
// }
// }
int q; cin >> q;
while (q--) {
int n,k; cin >> n >> k;
string s; cin >> s;
k = (n-1)-k; // 一致するものの個数
cout << slv(s,k) << "\n";
}
}
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3472kb
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: 9ms
memory: 3740kb
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