Submission #43917

#	Time	Username	Problem	Language	Result	Execution time	Memory
43917		Yehezkiel	Zagonetka (COI18_zagonetka)	C++11	100 / 100	89 ms	716 KiB

zagonetka

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define all(x) (x).begin(),(x).end()
typedef long long LL;
typedef pair<int,int> pii;
typedef long double LD;
const int MAXN=100;
const int batastanya=5000;
int pos[MAXN+5],totaltanya=0,n;
bool hubungan[MAXN+5][MAXN+5];
vector <int> awal,perm_min,perm_max;
void print(vector <int> v){
	for(int i=0;i<v.size();i++)
	{
		printf("%d",v[i]);
		if(i==(int) v.size()-1)
			printf("\n");
		else
			printf(" ");
	}
}
bool equal(vector <int> tanya){
	totaltanya++;
	assert(totaltanya<=batastanya);
	printf("query ");
	print(tanya);
	fflush(stdout);
	int respon;
	scanf("%d",&respon);
	return (respon);
}
void jawab(){
	printf("end\n");
	print(perm_min);
	print(perm_max);
}

void berhubungan(){
	memset(hubungan,false,sizeof(hubungan));
	int nomor;
	vector <int> temp;
	for(int i=2;i<=n;i++)			//cek hubungan 
	{
		for(int j=i-1;j>=1;j--)
		{
			//cout<<"ngecek antara "<<i<<" dengan "<<j<<endl;
			if(hubungan[i][j])			//terlah terhubung dengan pengantara
				continue;
			
			//lakukan penomoran aneh
			temp=awal;
			nomor=i;
			
			//penomoran yang musuh
			for(int k=i-1;k>=j;k--)
			{
				if(!hubungan[i][k])
					temp[pos[k]]=nomor--;
			}
			
			//penomoran yang berhubungan
			temp[pos[i]]=nomor--;
			for(int k=i-1;k>=j;k--)
			{
				if(hubungan[i][k])
					temp[pos[k]]=nomor--;
			}
			
			assert(nomor==j-1);
			if(!equal(temp))			//artinya wajib berhubungan
			{
				//ubah jadi transitive
				hubungan[i][j]=true;
				for(int k=j-1;k>=1;k--)
					if(hubungan[j][k])
						hubungan[i][k]=true;
				//cout<<"wah jadian "<<endl;
			}
		}
	}
}


vector <int> node[MAXN+5];
pair<vector <int>, vector <int> > pisahkan(vector <int> inti, vector <int> sub){			//kiri sisa inti, kanan yang sub
	vector <int> kiri,kanan;
	int j=0;
	for(int i=1;i<inti.size();i++)
	{
		while(j<sub.size()&&sub[j]<inti[i])
			j++;
		if(j<sub.size()&&sub[j]==inti[i])
			kanan.pb(inti[i]);
		else
			kiri.pb(inti[i]);
	}
	return mp(kiri,kanan);
}
void solve(vector <int> &setor,vector <int> anggota,vector <int> nomor){
	pair<vector<int> ,vector <int> > temp;
	vector <int> nomorlain;
	while(anggota.size())
	{
			/*cout<<"solving dengan anggota"<<endl;
			for(auto isi:anggota)
				cout<<isi<<" ";
			cout<<endl;
			cout<<"nomornya "<<endl;
			for(auto isi:nomor)
				cout<<isi<<" ";
			cout<<endl;*/
			
		temp=pisahkan(anggota,node[anggota[0]]);
		int delta=temp.se.size()+1;
		
		setor[anggota[0]]=nomor[delta-1];
		nomorlain.clear();
		for(int i=0;i<delta-1;i++)
			nomorlain.pb(nomor[i]);
		
		for(int i=0;i+delta<nomor.size();i++)
			nomor[i]=nomor[i+delta];
		nomor.resize((int) nomor.size()-delta);
		
		anggota=temp.fi;
		
		solve(setor,temp.se,nomorlain);
	}
}
void solve(){
	perm_min.resize(n);
	perm_max.resize(n);
	for(int ulang=0;ulang<2;ulang++)
	{
		for(int i=0;i<n;i++)
			node[i].clear();
		
		//construct graph
		for(int i=2;i<=n;i++)
		{
			for(int j=1;j<i;j++)
			{
				if(hubungan[i][j])
				{
					if(ulang==0)
						node[pos[i]].pb(pos[j]);
					else
						node[pos[j]].pb(pos[i]);
				}
			}
		}
		
		for(int i=0;i<n;i++)
			sort(all(node[i]));
		
		vector <int> anggota,nomor;
		for(int i=0;i<n;i++)
		{
			anggota.pb(i);
			nomor.pb(i+1);
		}
		
		if(ulang==0)
			solve(perm_min,anggota,nomor);
		else
			solve(perm_max,anggota,nomor);
			
		if(ulang==1)
		{
			for(auto &isi:perm_max)
				isi=n-isi+1;
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int input;
		scanf("%d",&input);
		pos[input]=awal.size();
		awal.pb(input);
	}
	assert(equal(awal));			//test test ji
	
	berhubungan();
	solve();
	jawab();
}

Compilation message (stderr)

zagonetka.cpp: In function 'void print(std::vector<int>)':
zagonetka.cpp:18:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++)
              ~^~~~~~~~~
zagonetka.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > pisahkan(std::vector<int>, std::vector<int>)':
zagonetka.cpp:93:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<inti.size();i++)
              ~^~~~~~~~~~~~
zagonetka.cpp:95:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<sub.size()&&sub[j]<inti[i])
         ~^~~~~~~~~~~
zagonetka.cpp:97:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j<sub.size()&&sub[j]==inti[i])
      ~^~~~~~~~~~~
zagonetka.cpp: In function 'void solve(std::vector<int>&, std::vector<int>, std::vector<int>)':
zagonetka.cpp:126:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i+delta<nomor.size();i++)
               ~~~~~~~^~~~~~~~~~~~~
zagonetka.cpp: In function 'bool equal(std::vector<int>)':
zagonetka.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&respon);
  ~~~~~^~~~~~~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:182:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
zagonetka.cpp:186:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&input);
   ~~~~~^~~~~~~~~~~~~

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