# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
110023521 |
Practice:
duyiblue |
1081F
- 22
|
GNU C++11
|
Accepted
|
62 ms
|
12 KB
|
2021-03-15 12:28:01 |
2021-03-15 12:28:01 |
|
// problem: CF1081F
#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }
const int MAXN = 300;
int n, m;
int ans[MAXN + 5];
int ask(int l, int r) {
cout << "? " << l << " " << r << endl;
int res;
cin >> res;
return res;
}
int work(int l, int r, int cur1, bool goalx = 1, bool goaly = 1, bool goalz = 0) {
// x, y, z 分别代表 [1, l), [l, r], (r, n] 三个部分
// 默认的 goal 是把 [1, r] 反转
assert(r % 2 != (n - l + 1) % 2);
bool x = 0, y = 0, z = 0; // 三个部分是否被翻转过
while (true) {
int res = ask(l, r);
int d = ((cur1 - res) % 2 + 2) % 2; // 1 的变化量的奇偶性
cur1 = res;
if (d % 2 == r % 2) {
x ^= 1;
y ^= 1;
} else { // d % 2 == (n - l + 1) % 2
y ^= 1;
z ^= 1;
}
if (x == goalx && y == goaly && z == goalz) {
return cur1;
}
}
}
int main() {
cin >> n >> m;
if (n == 1) {
ans[1] = m;
} else if (n % 2 == 0) {
int lst = 0;
for (int i = 1; i <= n; ++i) {
int cur1 = work(i, i, m);
int x = (m - cur1 + i);
assert(x % 2 == 0);
x /= 2;
ans[i] = x - lst;
lst = x;
int tmp = work(i, i, cur1);
assert(tmp == m);
}
} else {
int cur1 = work(2, n, m, 0, 1, 1); // 把 [2, n] 反转
int x = (m + cur1 - (n - 1));
assert(x % 2 == 0);
x /= 2;
assert(x <= 1);
ans[1] = x;
int tmp = work(2, n, cur1, 0, 1, 1);
assert(tmp == m);
int lst = x;
for (int i = 2; i <= n; ++i) {
int cur1 = work(i - 1, i, m);
int x = (m - cur1 + i);
assert(x % 2 == 0);
x /= 2;
ans[i] = x - lst;
lst = x;
int tmp = work(i - 1, i, cur1);
assert(tmp == m);
}
}
cout << "! ";
for (int i = 1; i <= n; ++i) {
cout << ans[i];
}
cout << endl;
return 0;
}
Click to see test details