Submission #1254190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254190		ifugao	Light Bulbs (EGOI24_lightbulbs)	C++20	60.63 / 100	31 ms	420 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int N;
string allZero;

int test_row(int rowId,string& choice)
{
	cout << "?" << endl;
	for(int i=0;i<N;i++)
	{
		if(i==rowId)
			cout << choice << endl;
		else
			cout << allZero << endl;
	}
	int litCells;
	cin >> litCells;
	return litCells;
}

int test_horizontal_aux(int row1,int row2, int col)
{
	cout << "?" << endl;
	for(int i=0;i<N;i++)
	{
		if(i==row1 || i==row2)
		{
			allZero[col]='1';
			cout << allZero << endl;
			allZero[col]='0';
		}
		else
			cout << allZero << endl;
	}
	int litCells;
	cin >> litCells;
	return litCells;
}

bool test_horizontal(int row,int col)
{
	for(int offset=1;offset<=2;offset++)
	{
		int litCells=test_horizontal_aux(row,(row+offset)%N,col);
		if(litCells==2*N)
			return true;
		else if(litCells==N)
			return false;
	}
	int litCells=test_horizontal_aux((row+1)%N,(row+2)%N,col);
	if(litCells==2*N)
		return false;
	else if(litCells==N)
		return true;
	assert(false);
}

bool test_horizontal2(int row,int col, int colFirst)
{
	assert(row>0);
	cout << "?" << endl;
	for(int i=0;i<N;i++)
	{
		if(i==0)
		{
			allZero[colFirst]='1';
			cout << allZero << endl;
			allZero[colFirst]='0';
		}
		else if(i==row)
		{
			allZero[col]='1';
			cout << allZero << endl;
			allZero[col]='0';
		}
		else
			cout << allZero << endl;
	}
	int litCells;
	cin >> litCells;
	return (litCells==2*N);
}

void full_row(int rowId)
{
	cout << "!" << endl;
	for(int i=0;i<N;i++)
	{
		if(i==rowId)
			cout << string(N,'1') << endl;
		else
			cout << allZero << endl;
	}
}

void print_picked(vector<int>& picked)
{
	cout << "!" << endl;
	for(int i=0;i<N;i++)
	{
		allZero[picked[i]]='1';
		cout << allZero << endl;
		allZero[picked[i]]='0';
	}
}

int cut_half(int cnt,string& choice,string& prevChoice)
{
	int curCnt=0;
	for(int j=0;j<N;j++)
	{
		if(prevChoice[j]=='1' && curCnt<(cnt+1)/2)
		{
			choice[j]='1';
			curCnt++;
		}
		else
			choice[j]='0';
	}
	return curCnt;
}

void other_half(int& curCnt,string& choice,string& prevChoice)
{
	curCnt=0;
	for(int j=0;j<N;j++)
	{
		if(prevChoice[j]=='1' && choice[j]=='0')
		{
			choice[j]='1';
			curCnt++;
		}
		else
			choice[j]='0';
	}
}

int main()
{
	cin >> N;
	allZero=string(N,'0');
	vector<int> picked(N,-1);
	for(int i=0;i<N;i++)
	{
		// Try whole row
		string choice(N,'1');
		string prevChoice=choice;
		int cnt=N;
		int litCells=test_row(i,choice);
		if(litCells==N*N)
		{
			full_row(i);
			exit(0);
		}
		while(cnt>1)
		{
			int curCnt=cut_half(cnt,choice,prevChoice);
			if(curCnt==1)
			{
				int col=choice.find('1');
				if((i==0 && test_horizontal(i,col)) || (i>0 && test_horizontal2(i,col,picked[0])))
				{
					picked[i]=col;
					break;
				}
				else
				{
					other_half(curCnt,choice,prevChoice);
				}
			}
			else
			{
				litCells=test_row(i,choice);
				if(litCells==N)
				{
					picked[i]=choice.find('1');
					break;
				}
				else if(litCells==N*curCnt)
				{
					other_half(curCnt,choice,prevChoice);
				}
			}
			prevChoice=choice;
			cnt=curCnt;
		}
		if(cnt==1)
			picked[i]=prevChoice.find('1');
		else
			assert(picked[i]!=-1);
	}
	print_picked(picked);
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 38.6344 / 78