Основное
 
 
Отправитель Задача Язык Вердикт Время Память Отослано Протест.  
110023521 Дорешивание:
duyiblue
1081F - 22 GNU C++11 Полное решение 62 мс 12 КБ 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;
}
?
Время: ? ms, память: ? КБ
Вердикт: ?
Ввод
?
Вывод участника
?
Ответ жюри
?
Комментарий чекера
?
Диагностика
?
Показать детали тестирования