Submission #601897

#	Time	Username	Problem	Language	Result	Execution time	Memory
601897		Jasiekstrz	Zagonetka (COI18_zagonetka)	C++17	100 / 100	135 ms	356 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];
vector<int> need[N+10];
bool vis[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 dfs1(int x,vector<int> &ans,int n)
{
	vis[x]=true;
	for(int i=1;i<=n;i++)
	{
		if(!vis[g[i]] && edg[i][tab[x]])
		{
			ans.push_back(g[i]);
			dfs1(g[i],ans,n);
		}
	}
	return;
}
void srt1(int x)
{
	static int nr=1;
	while(!need[x].empty())
	{
		if(tmp[need[x].back()]==0)
			srt1(need[x].back());
		need[x].pop_back();
	}
	tmp[x]=nr++;
	return;
}
void srt1_(int n)
{
	for(int i=1;i<=n;i++)
		tmp[i]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			vis[j]=false;
		need[i].clear();
		dfs1(i,need[i],n);
		sort(need[i].begin(),need[i].end());
		reverse(need[i].begin(),need[i].end());
	}
	for(int i=1;i<=n;i++)
	{
		if(tmp[i]==0)
			srt1(i);
	}
	return;
}
void dfs2(int x,vector<int> &ans,int n)
{
	vis[x]=true;
	for(int i=1;i<=n;i++)
	{
		if(!vis[g[i]] && edg[tab[x]][i])
		{
			ans.push_back(g[i]);
			dfs2(g[i],ans,n);
		}
	}
	return;
}
void srt2(int x,int n)
{
	static int nr=-1;
	if(nr==-1)
		nr=n;
	while(!need[x].empty())
	{
		if(tmp[need[x].back()]==0)
			srt2(need[x].back(),n);
		need[x].pop_back();
	}
	tmp[x]=nr--;
	return;
}
void srt2_(int n)
{
	for(int i=1;i<=n;i++)
		tmp[i]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			vis[j]=false;
		need[i].clear();
		dfs2(i,need[i],n);
		sort(need[i].begin(),need[i].end());
		reverse(need[i].begin(),need[i].end());
	}
	for(int i=1;i<=n;i++)
	{
		if(tmp[i]==0)
			srt2(i,n);
	}
	return;
}
void srt(int n,int c)
{
	if(c==-1)
		srt1_(n);
	else
		srt2_(n);
	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;

			if(tmp[g[i]]<tmp[g[j]])
			{
				edg[i][j]=true;
				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<<g[i]<<" "<<g[j]<<" ("<<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: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 51 / 51