QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #236280 | #6442. Secret of Tianqiu Valley | ucup-team1001 | RE | 1ms | 3392kb | C++23 | 6.4kb | 2023-11-03 19:47:51 | 2023-11-03 19:47:51 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define endl "\n"
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
void solve() {
int n;
cin >> n;
string s;
cin >> s;
vector<int> vis(n);
vector<int> ans(n);
auto is0 = [&](int i) {
return !((s[i] - '0') ^ (vis[i] % 2));
};
rep(i, 0, n - 2) {
if (is0(i)) {
vis[i]++;
vis[i + 1]++;
vis[i + 2]++;
ans[i + 1]++;
}
}
int k = n / 3;
int last2 = (1 - is0(n - 2)) * 2 + (1 - is0(n - 1));
// rep(i, 0, n) {
// cout << ans[i] << " ";
// }
// cout << endl;
// rep(i, 0, n) {
// cout << (is0(i) ? '0' : '1');
// }
// cout << endl;
// rep(i, 0, n) {
// cout << vis[i] << " ";
// }
// cout << endl;
// cout << last2 << endl;
switch (n % 3) {
case 0: {
switch (last2) {
case 0b00:
case 0b01:
case 0b10: {
cout << "0\n";
return;
}
case 0b11: {
rep(i, 0, n) {
ans[i]++;
}
break;
}
}
break;
}
case 1: {
switch (last2) {
case 0b00: {
rep(i, 0, k) {
ans[3 * i + 2]++;
}
ans[n - 1]++;
break;
}
case 0b01: {
rep(i, 0, k) {
ans[3 * i]++;
}
break;
}
case 0b10: {
rep(i, 0, k) {
ans[3 * i + 1]++;
}
break;
}
case 0b11: {
rep(i, 0, n) {
ans[i]++;
}
break;
}
}
break;
}
case 2: {
switch (last2) {
case 0b00: {
rep(i, 0, k) {
ans[3 * i + 1]++;
}
break;
}
case 0b01: {
rep(i, 0, k) {
ans[3 * i + 2]++;
}
ans[n - 1]++;
break;
}
case 0b10: {
rep(i, 0, k) {
ans[3 * i + 3]++;
}
ans[0]++;
break;
}
case 0b11: {
rep(i, 0, n) {
ans[i]++;
}
break;
}
}
break;
}
}
// rep(i, 0, n) {
// cout << ans[i] << " ";
// }
// cout << endl;
// vector<int> ans_v;
// rep(i, 0, n) {
// if (!(ans[i] % 2))ans_v.emplace_back(i + 1);
// }
// n = (int) ans_v.size();
// cout << n << endl;
// rep(i, 0, n) {
// cout << ans_v[i] << " \n"[i == n - 1];
// }
set<int> ans0, ans1, nans0;
rep(i, 0, n) {
if (!(ans[i] % 2)) {
if (s[i] == '0') {
ans0.emplace(i);
} else {
ans1.emplace(i);
}
} else {
if (s[i] == '0') {
nans0.emplace(i);
}
}
}
vector<int> ans_v;
while (!ans0.empty() || !nans0.empty()) {
// cout << "ans0:";
// for (auto i: ans0) {
// cout << i + 1 << " ";
// }
// cout << endl;
// cout << "ans1:";
// for (auto i: ans1) {
// cout << i + 1 << " ";
// }
// cout << endl;
// cout << "nans0:";
// for (auto i: nans0) {
// cout << i + 1 << " ";
// }
// cout << endl;
// cout << "ans_v:";
// for (auto i: ans_v) {
// cout << i + 1 << " ";
// }
// cout << endl;
// cout << endl;
if (ans0.empty()) {
auto t = *nans0.begin();
nans0.erase(nans0.begin());
ans_v.emplace_back(t);
ans1.emplace(t);
if (auto i = ans1.find((t + n - 1) % n);i != ans1.end()) {
ans0.emplace(*i);
ans1.erase(i);
} else if (i = nans0.find((t + n - 1) % n);i != ans1.end()) {
nans0.erase(i);
} else {
nans0.emplace((t + n - 1) % n);
}
if (auto i = ans1.find((t + 1) % n);i != ans1.end()) {
ans0.emplace(*i);
ans1.erase(i);
} else if (i = nans0.find((t + 1) % n);i != nans0.end()) {
nans0.erase(i);
} else {
nans0.emplace((t + 1) % n);
}
} else {
auto t = *ans0.begin();
ans0.erase(ans0.begin());
ans_v.emplace_back(t);
if (auto i = ans0.find((t + n - 1) % n);i != ans0.end()) {
ans1.emplace(*i);
ans0.erase(i);
} else if (i = ans1.find((t + n - 1) % n);i != ans1.end()) {
ans0.emplace(*i);
ans1.erase(i);
} else if (i = nans0.find((t + n - 1) % n);i != nans0.end()) {
nans0.erase(i);
} else {
nans0.emplace((t + n - 1) % n);
}
if (auto i = ans0.find((t + 1) % n);i != ans0.end()) {
ans1.emplace(*i);
ans0.erase(i);
} else if (i = ans1.find((t + 1) % n);i != ans1.end()) {
ans0.emplace(*i);
ans1.erase(i);
} else if (i = nans0.find((t + 1) % n);i != nans0.end()) {
nans0.erase(i);
} else {
nans0.emplace((t + 1) % n);
}
}
}
n = (int) ans_v.size();
cout << n << endl;
rep(i, 0, n) {
cout << ans_v[i] + 1 << " \n"[i == n - 1];
}
}
int main() {
// IOS
int t;
cin >> t;
while (t--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3388kb
input:
2 5 00000 3 001
output:
7 1 3 2 1 5 1 4 0
result:
ok all puzzle solved (2 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3384kb
input:
7 3 000 3 100 3 010 3 110 3 001 3 101 3 011
output:
1 2 0 0 0 0 0 0
result:
ok all puzzle solved (7 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3392kb
input:
15 4 0000 4 1000 4 0100 4 1100 4 0010 4 1010 4 0110 4 1110 4 0001 4 1001 4 0101 4 1101 4 0011 4 1011 4 0111
output:
4 1 3 2 4 1 3 1 4 4 3 2 1 3 1 1 2 2 4 4 1 2 1 3 3 4 1 3 1 2 4 2 1 2 4 2 1 3 3 3 2 4 4 1 4 1 3 3 2 1 3 3 1 2 4
result:
ok all puzzle solved (15 test cases)
Test #4:
score: -100
Runtime Error
input:
31 5 00000 5 10000 5 01000 5 11000 5 00100 5 10100 5 01100 5 11100 5 00010 5 10010 5 01010 5 11010 5 00110 5 10110 5 01110 5 11110 5 00001 5 10001 5 01001 5 11001 5 00101 5 10101 5 01101 5 11101 5 00011 5 10011 5 01011 5 11011 5 00111 5 10111 5 01111
output:
7 1 3 2 1 5 1 4 2 2 5 2 1 3 1 4 2 2 4 3 2 1 3 1 5 6 4 3 2 1 2 5 2 3 5 3 5 1 4 3 3 2 4 4 3 2 1 3 1 1