Submission #1296483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296483		PieArmy	How to Avoid Disqualification in 75 Easy Steps (CEOI23_avoid)	C++20	25 / 100	2 ms	448 KiB

avoid

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#include"avoid.h"

//send(vector<int>)
//vector<int>wait()
mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());

int n=1000;

pair<int,int> scout(int R,int H){
	if(R==10){
		vector<int>v[10];
		for(int i=1;i<=n;i++){
			for(int j=0;j<10;j++){
				if((i>>j)&1)v[j].pb(i);
			}
		}
		for(int i=0;i<10;i++){
			send(v[i]);
		}
		vector<int>res=wait();
		int cev=0;
		for(int i=0;i<10;i++){
			if(res[i])cev+=(1<<i);
		}
		return {cev,cev};
	}
	else if(R==20){
		pair<int,int>p;
		int l=1,r=1000;
		while(l<r){
			int mi=(l+r)/2;
			vector<int>v;
			for(int i=1;i<=mi;i++){
				v.pb(i);
			}
			send(v);
			if(wait()[0])r=mi;
			else l=mi+1;
		}
		p.fr=l;
		l=1;r=1000;
		while(l<r){
			int mi=(l+r+1)/2;
			vector<int>v;
			for(int i=mi;i<=n;i++){
				v.pb(i);
			}
			send(v);
			if(wait()[0])l=mi;
			else r=mi-1;
		}
		p.sc=l;
		return p;
	}
	else if(R==30){
		vector<int>v[10];
		for(int i=1;i<=n;i++){
			for(int j=0;j<10;j++){
				if((i>>j)&1)v[j].pb(i);
			}
		}
		for(int i=0;i<10;i++){
			send(v[i]);
			v[i].clear();
		}
		for(int i=1;i<=n;i++){
			for(int j=0;j<10;j++){
				if(!((i>>j)&1))v[j].pb(i);
			}
		}
		for(int i=0;i<10;i++){
			send(v[i]);
			v[i].clear();
		}
		vector<int>res=wait();
		int mask=0;
		for(int i=0;i<20;i++){
			if(i<10){
				if(res[i])mask+=(1<<i);
			}
			else if(res[i]==0){
				if(mask&(1<<(i-10))){
					mask-=(1<<(i-10));
				}
			}
		}
		if(mask==0){
			int cev=0;
			for(int i=0;i<10;i++){
				if(res[i])cev+=(1<<i);
			}
			return {cev,cev};
		}
		vector<int>can;
		for(int i=1;i<=n;i++){
			if(i<(i^mask)){
				can.pb(i);
			}
		}
		for(int i=0;i<can.size();i++){
			for(int j=0;j<10;j++){
				if((i>>j)&1)v[j].pb(can[i]);
			}
		}
		for(int i=0;i<10;i++){
			send(v[i]);
			v[i].clear();
		}
		res=wait();
		int tar=0;
		for(int i=0;i<10;i++){
			if(res[i])tar+=(1<<i);
		}
		return {can[tar],can[tar]^mask};
	}
	else{
		vector<int>per(1000);
		iota(per.begin(),per.end(),1);
		shuffle(per.begin(),per.end(),rng);
		vector<int>v[10];
		for(int i=0;i<n;i++){
			for(int j=0;j<10;j++){
				if((i>>j)&1)v[j].pb(per[i]);
			}
		}
		for(int i=0;i<10;i++){
			send(v[i]);
			v[i].clear();
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<10;j++){
				if(!((i>>j)&1))v[j].pb(per[i]);
			}
		}
		for(int i=0;i<10;i++){
			send(v[i]);
			v[i].clear();
		}
		for(int i=1;i<1000;i*=10){
			for(int j=0;j<10;j++){
				vector<int>v2;
				for(int l=0;l<n;l++){
					if(((l/i)%10)==j)v2.pb(per[l]);
				}
				send(v2);
			}
		}
		vector<int>res=wait();
		int mask=0;
		for(int i=0;i<20;i++){
			if(i<10){
				if(res[i])mask+=(1<<i);
			}
			else if(res[i]==0){
				if(mask&(1<<(i-10))){
					mask-=(1<<(i-10));
				}
			}
		}
		if(mask==0){
			int cev=0;
			for(int i=0;i<10;i++){
				if(res[i])cev+=(1<<i);
			}
			return {cev,cev};
		}
		vector<pair<int,int>>on(3,{-1,-1});
		for(int i=20;i<50;i++){
			if(res[i]){
				on[(i-20)/10].fr=(i-20)%10;
				swap(on[(i-20)/10].fr,on[(i-20)/10].sc);
			}
		}
		for(int i=0;i<3;i++){
			if(on[i].fr==-1)on[i].fr=on[i].sc;
		}
		for(int i=0;i<4;i++){
			int x=on[0].fr,y=on[0].sc;
			if(i&1){
				x+=10*on[1].sc;
				y+=10*on[1].fr;
			}
			else{
				x+=10*on[1].fr;
				y+=10*on[1].sc;
			}
			if(i&2){
				x+=100*on[2].sc;
				y+=100*on[2].fr;
			}
			else{
				x+=100*on[2].fr;
				y+=100*on[2].sc;
			}
			if((x^y)==mask){
				return {per[x],per[y]};
			}
		}
	}
}

Compilation message (stderr)

avoid.cpp: In function 'std::pair<int, int> scout(int, int)':
avoid.cpp:208:1: warning: control reaches end of non-void function [-Wreturn-type]
  208 | }
      | ^

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 0 / 75