Submission #1365274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1365274		weedywelon	Dark Ride (EGOI25_darkride)	C++20	100 / 100	2 ms	480 KiB

Main

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;

//all on except 1: if end, 1 scream. if not, 2 scream
//only flipping rooms 0,n-1 will switch the parity of #screams

//phase 1: identify lsb at which A,B differ. k turns, where k=lsb
//phase 2: identify lowest k-1 bits using bsearch. k-1 turns
//phase 3: identify 15-k bits for both A,B. 2(15-k) turns
//tot=29 turns??

const int MAXLG=15;
signed main(){
	int n; cin>>n;
	
	//phase 1: find lsb diff
	int k=-1;
	for (int i=0; i<MAXLG; i++){
		string s;
		FOR(j,n){
			if (j&(1<<i)) s+="1";
			else s+="0";
		}
		cout<<"? "<<s<<endl;
		
		int a; cin>>a;
		if (a%2==1){
			k=i;
			break;
		}
	}
	
	//phase 2: find first k-1 bits
	int on[k];
	memset(on,0,sizeof(on));
	
	for (int i=0; i<k; i++){
		string s;
		FOR(j,n){
			if ((j&(1<<k)) && (j&(1<<i))) s+="1";
			else s+="0";
		}
		cout<<"? "<<s<<endl;
		
		int a; cin>>a;
		if (a%2==1) on[i]=1;
	}
	
	//phase 3: find v1, v2
	int v0=0,v1=0;
	FOR(i,k) if (on[i]){
		v0|=(1<<i);
		v1|=(1<<i);
	}
	v1|=(1<<k);

	int MOD=(1<<(k+1));
	for (int i=k+1; i<15; i++){
		string s;
		FOR(j,n){
			if (j%MOD!=v0%MOD) s+="0";
			else if (j&(1<<i)) s+="1";
			else s+="0";
		}
		cout<<"? "<<s<<endl;
		
		int a; cin>>a;
		if (a%2==1) v0|=(1<<i);
	}
	
	for (int i=k+1; i<15; i++){
		string s;
		FOR(j,n){
			if (j%MOD!=v1%MOD) s+="0";
			else if (j&(1<<i)) s+="1";
			else s+="0";
		}
		cout<<"? "<<s<<endl;
		
		int a; cin>>a;
		if (a%2==1) v1|=(1<<i);
	}
	
	cout<<"! "<<v0<<" "<<v1<<endl;
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/string.h:548,
                 from /usr/include/c++/13/cstring:42,
                 from Main.cpp:3:
In function 'void* memset(void*, int, size_t)',
    inlined from 'int main()' at Main.cpp:67:8:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:59:33: warning: 'void* __builtin_memset(void*, int, long unsigned int)' specified bound 18446744073709551612 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
   59 |   return __builtin___memset_chk (__dest, __ch, __len,
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
   60 |                                  __glibc_objsize0 (__dest));
      |                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 15 / 15
• Subtask 4: 17 / 17
• Subtask 5: 16 / 16
• Subtask 6: 14 / 14
• Subtask 7: 29 / 29