oj.uz

Submission #601897

# Submission time Handle Problem Language Result Execution time Memory
601897 2022-07-22T12:01:05 Z Jasiekstrz Zagonetka (COI18_zagonetka) C++17
100 / 100
 135 ms 356 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 208 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 256 KB Output is correct
2 Correct 35 ms 356 KB Output is correct
3 Correct 45 ms 324 KB Output is correct
4 Correct 51 ms 284 KB Output is correct
5 Correct 13 ms 208 KB Output is correct
6 Correct 47 ms 288 KB Output is correct
7 Correct 6 ms 208 KB Output is correct
8 Correct 8 ms 208 KB Output is correct
9 Correct 48 ms 288 KB Output is correct
10 Correct 26 ms 292 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 244 KB Output is correct
3 Correct 6 ms 208 KB Output is correct
4 Correct 6 ms 208 KB Output is correct
5 Correct 5 ms 208 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 7 ms 208 KB Output is correct
9 Correct 8 ms 252 KB Output is correct
10 Correct 3 ms 212 KB Output is correct
11 Correct 9 ms 208 KB Output is correct
12 Correct 8 ms 208 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 292 KB Output is correct
2 Correct 99 ms 308 KB Output is correct
3 Correct 95 ms 356 KB Output is correct
4 Correct 16 ms 304 KB Output is correct
5 Correct 24 ms 312 KB Output is correct
6 Correct 29 ms 296 KB Output is correct
7 Correct 41 ms 308 KB Output is correct
8 Correct 60 ms 296 KB Output is correct
9 Correct 44 ms 308 KB Output is correct
10 Correct 107 ms 292 KB Output is correct
11 Correct 77 ms 296 KB Output is correct
12 Correct 108 ms 296 KB Output is correct
13 Correct 88 ms 292 KB Output is correct
14 Correct 93 ms 292 KB Output is correct
15 Correct 135 ms 296 KB Output is correct
16 Correct 115 ms 292 KB Output is correct