Submission #1343691

#TimeUsernameProblemLanguageResultExecution timeMemory
1343691ByeWorldDark Ride (EGOI25_darkride)C++20
100 / 100
3 ms1528 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "Ofast")
#define int long long
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 5e5+10;
const int MAXA = 5e4+10;
const int SQRT = 300;
const ll INF = 2e18;
const int MOD = 1e9+7;
const int LOG = 32;
ll sum(auto a, auto b){ 
	ll te = a+MOD+b; 
	for(; te >= MOD; ) te -= MOD;
	return te;
}
void chsum(auto &a, auto b){ a = sum(a,b); }
ll mul(auto a, auto b){ return 1ll*a*b%MOD; }
void chmul(auto &a, auto b){ a = mul(a,b); }
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }

ll expo(int a, int b){
	if(b==0) return 1;
	ll te = expo(a, b/2); te = mul(te,te); // temporary -> te
	return (b%2 ? mul(te, a) : te);
}
vector <int> dx = {0, 0, -1, 1};
vector<int> dy = {-1, 1, 0, 0};

int n, A=-1, B=-1;

int solve(vector<int> vec){
	int l=0, r=vec.size()-1, mid=0, cnt=-1;
	while(l<=r){
		mid = md;
		string s(n, '0');
		for(int j=0; j<=mid; j++){
			s[vec[j]] = '1';
		}
		cout << "? " << s << endl;
		int x; cin>>x;
		if(x%2 == 1){
			// beda jenis, ada
			cnt = mid; r = mid-1;
		} else l = mid+1; // sama jenis
 	}
 	return vec[cnt];
}
vector<int> a, b;
int ty[MAXN];

bool div(vector<int> vec, vector<int> vec2, int id){
	string s(n, '0');
	for(int j=0; j<vec.size(); j++){
		s[vec[j]] = '1';
	}
	cout << "? " << s << endl;
	int x; cin>>x;
	ty[id] = x%2;
	if(x%2 == 1){
		// beda jenis, kelar
		a = vec; b = vec2;
		return 1;
	}
	return 0;
}
signed main(){ 
	// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	int id = 0;
	while(true){
		if((1<<(id+1)) >= n) break;
		id++;
	}
	// cout << id << " id\n";
	for(int i=0; i<=id; i++){
		vector<int> vec, vec2;
		
		for(int j=0; j<n; j++){
			if((j>>i) & 1) vec.pb(j);
			else vec2.pb(j);
		}
		div(vec, vec2, i);
	}
	A = solve(a);
	int B = 0;
	for(int i=0; i<=id; i++){
		int g = ((A>>i) & 1);
		// cout << i << ' '<< g << ' '<< ty[i] << " ty\n";
		g ^= ty[i];
		if(g) B += (1<<i);
	}

	cout << "! " << A << ' ' << B << endl;
} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...