Submission #601444

#	Time	Username	Problem	Language	Result	Execution time	Memory
601444		Jasiekstrz	Zagonetka (COI18_zagonetka)	C++17	9 / 100	84 ms	308 KiB

zagonetka

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=100;
int tab[N+10];
int g[N+10];
int tmp[N+10];
bool edg[N+10][N+10];
int deg[N+10];
void topo(int l,int r)
{
	priority_queue<int> pq;
	for(int i=l;i<=r;i++)
	{
		deg[i]=0;
		for(int j=l;j<i;j++)
			deg[i]+=edg[j][i];
		if(deg[i]==0)
		{
			pq.emplace(i);
			deg[i]=-1;
		}
	}
	int it=l;
	while(!pq.empty())
	{
		auto x=pq.top();
		pq.pop();
		tmp[g[x]]=it++;
		for(int i=x+1;i<=r;i++)
		{
			deg[i]-=edg[x][i];
			if(deg[i]==0)
			{
				pq.emplace(i);
				deg[i]=-1;
			}
		}
	}
	return;
}
void srt(int n,int c)
{
	priority_queue<int> pq;
	for(int i=1;i<=n;i++)
	{
		deg[i]=0;
		for(int j=1;j<i;j++)
			deg[i]+=edg[j][i];
		if(deg[i]==0)
		{
			pq.push(g[i]*c);
			deg[i]=-1;
		}
	}
	int it=1;
	while(!pq.empty())
	{
		auto gx=pq.top();
		pq.pop();
		gx/=c;
		tmp[gx]=it++;
		auto x=tab[gx];
		for(int i=x+1;i<=n;i++)
		{
			deg[i]-=edg[x][i];
			if(deg[i]==0)
			{
				pq.emplace(g[i]*c);
				deg[i]=-1;
			}
		}
	}
	return;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>tab[i];
		g[tab[i]]=i;
	}
	for(int j=2;j<=n;j++)
	{
		for(int i=j-1;i>=1;i--)
		{
			for(int k=1;k<=n;k++)
				tmp[k]=tab[k];
			topo(i,j);

			//cerr<<i<<" "<<j<<endl;
			//for(int k=1;k<=n;k++)
			//	cerr<<tmp[k]<<" ";
			//cerr<<endl;

			for(int k=1;k<=n;k++)
			{
				if(tmp[g[k]]==i)
				{
					edg[i][j]=true;
					break;
				}
				if(tmp[g[k]]==j)
				{
					edg[i][j]=false;
					break;
				}
			}
			if(edg[i][j])
				continue;
			cout<<"query ";
			for(int k=1;k<=n;k++)
				cout<<tmp[k]<<" ";
			cout<<endl;
			cout.flush();
			bool w;
			cin>>w;
			if(!w)
				edg[i][j]=true;
			else
				edg[i][j]=false;
		}
	}

	//cerr<<endl;
	//for(int i=1;i<=n;i++)
	//{
	//	for(int j=i+1;j<=n;j++)
	//	{
	//		if(edg[i][j])
	//			cerr<<i<<" "<<j<<endl;
	//	}
	//}
	//cerr<<endl;

	cout<<"end"<<endl;
	for(int it:{-1,1})
	{
		for(int i=1;i<=n;i++)
			tmp[i]=tab[i];
		srt(n,it);
		for(int i=1;i<=n;i++)
			cout<<tmp[i]<<" ";
		cout<<endl;
	}
	cout.flush();
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 51