제출 #1254228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254228		ifugao	Light Bulbs (EGOI24_lightbulbs)	C++20	60.67 / 100	30 ms	420 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int N;
string allZero;
int knownCol=-1;

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);
}

bool test_vertical2(int row,int col, int rowKnown)
{
	cout << "?" << endl;
	for(int i=0;i<N;i++)
	{
		string s(N,'0');
		if(i==row)
			s[col]='1';
		if(i==rowKnown)
			s[knownCol]='1';
		cout << s << 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_row(vector<int>& picked)
{
	cout << "!" << endl;
	for(int i=0;i<N;i++)
	{
		allZero[picked[i]]='1';
		cout << allZero << endl;
		allZero[picked[i]]='0';
	}
}

void try_print_picked_col(vector<int>& picked)
{
	for(int i=0;i<N;i++)
		if(picked[i]==-1)
			return;
		else
			knownCol=i;
	cout << "!" << endl;
	for(int i=0;i<N;i++)
	{
		string row(N,'0');
		for(int j=0;j<N;j++)
			if(picked[j]==i)
				row[j]='1';
		cout << row << endl;
	}
	exit(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> pickedRow(N,-1),pickedCol(N,-1);
	for(int i=0;i<N;i++)
	{
		// Try noncovered row
		string choice(N,'0');
		int cnt=0;
		for(int j=0;j<N;j++)
			if(pickedCol[j]==-1)
			{
				choice[j]='1';
				cnt++;
			}
		if(cnt==1)
		{
			int col=choice.find('1');
			assert(knownCol!=-1);
			if(test_vertical2(i,col,pickedCol[knownCol]))
			{
				pickedCol[col]=i;
				try_print_picked_col(pickedCol);
			}
			else
			{
				pickedRow[i]=col;
			}
		}
		else
		{
			string prevChoice=choice;
			int litCells=test_row(i,choice);
			if(litCells==cnt*N)
			{
				for(int j=0;j<N;j++)
					if(choice[j]=='1')
						pickedCol[j]=i;
				try_print_picked_col(pickedCol);
			}
			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,pickedRow[0])))
					{
						pickedRow[i]=col;
						break;
					}
					else
					{
						pickedCol[col]=i;
						try_print_picked_col(pickedCol);
						other_half(curCnt,choice,prevChoice);
					}
				}
				else
				{
					litCells=test_row(i,choice);
					if(litCells==N)
					{
						pickedRow[i]=choice.find('1');
						break;
					}
					else if(litCells==N*curCnt)
					{
						for(int j=0;j<N;j++)
							if(choice[j]=='1')
								pickedCol[j]=i;
						try_print_picked_col(pickedCol);
						other_half(curCnt,choice,prevChoice);
					}
				}
				prevChoice=choice;
				cnt=curCnt;
			}
			if(cnt==1)
				pickedRow[i]=prevChoice.find('1');
			else
				assert(pickedRow[i]!=-1);
		}
	}
	print_picked_row(pickedRow);
}

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