QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#140942 | #5156. Going in Circles | RetiredButNotTired# | WA | 1ms | 3504kb | C++20 | 1.7kb | 2023-08-17 00:26:44 | 2023-08-17 00:26:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int tt, tc;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
char go_right() {
cout << "? right" << endl;
char c;
cin >> c;
return c;
}
void flip() {
cout << "? flip" << endl;
char c;
cin >> c;
}
void answer(int n) {
cout << "! " << n << endl;
}
void solve() {
string mt;
char c;
cin >> c;
if (rand(0, 1)) {
flip();
mt.push_back(char('1' + '0' - c));
} else mt.push_back(c);
for (int i = 0; i < 149; i++) {
char c = go_right();
if (i < 49) {
if (rand(0, 1)) {
flip();
c = '1' + '0' - c;
}
mt.push_back(c);
} else mt.push_back(c);
}
bool atmost50 = false;
for (int len = 1; len <= 50; len++) {
string suf = mt.substr((int)mt.size() - len, len);
int number = 0;
for (int i = (int)mt.size() - len; i >= 0; i -= len)
number += (mt.substr(i, len) == suf);
if (number >= 3) atmost50 = true;
}
if (atmost50) {
for (int i = 0; i < 50; i++) {
char c = go_right();
if (c == '1') flip();
}
if (go_right() == '0') flip();
int ctr = 1;
while (go_right() != '1') {
ctr++;
}
answer(ctr);
} else {
assert((int)mt.size() == 150);
int i = 50;
for (; i + 49 < (int)mt.size(); i++)
if (mt.substr(i, 50) == mt.substr(0, 50)) return void(answer(i));
for (;; i++) {
mt.push_back(go_right());
if (mt.substr(i, 50) == mt.substr(0, 50)) return void(answer(i));
}
assert(false);
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
tt = 1, tc = 1; // cin >> tt;
while (tt--) solve(), tc++;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3504kb
input:
0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 1 0 1 0 1 ...
output:
? right ? right ? right ? flip ? right ? flip ? right ? right ? right ? right ? right ? flip ? right ? flip ? right ? flip ? right ? right ? right ? flip ? right ? flip ? right ? right ? right ? flip ? right ? right ? right ? flip ? right ? flip ? right ? right ? flip ? right ? right ? flip ? right ...
result:
wrong answer Wrong answer: incorrect guess 1 (ans: 5000). Queries used: 250