oj.uz

Submission #43917

# Submission time Handle Problem Language Result Execution time Memory
43917 2018-03-28T05:47:04 Z Yehezkiel Zagonetka (COI18_zagonetka) C++11
100 / 100
 89 ms 716 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 244 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 456 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 588 KB Output is correct
2 Correct 29 ms 588 KB Output is correct
3 Correct 39 ms 588 KB Output is correct
4 Correct 49 ms 588 KB Output is correct
5 Correct 10 ms 588 KB Output is correct
6 Correct 38 ms 588 KB Output is correct
7 Correct 6 ms 588 KB Output is correct
8 Correct 8 ms 592 KB Output is correct
9 Correct 25 ms 716 KB Output is correct
10 Correct 15 ms 716 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 6 ms 716 KB Output is correct
4 Correct 6 ms 716 KB Output is correct
5 Correct 3 ms 716 KB Output is correct
6 Correct 5 ms 716 KB Output is correct
7 Correct 6 ms 716 KB Output is correct
8 Correct 4 ms 716 KB Output is correct
9 Correct 17 ms 716 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 6 ms 716 KB Output is correct
12 Correct 5 ms 716 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 716 KB Output is correct
2 Correct 89 ms 716 KB Output is correct
3 Correct 64 ms 716 KB Output is correct
4 Correct 6 ms 716 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 5 ms 716 KB Output is correct
7 Correct 19 ms 716 KB Output is correct
8 Correct 33 ms 716 KB Output is correct
9 Correct 23 ms 716 KB Output is correct
10 Correct 80 ms 716 KB Output is correct
11 Correct 74 ms 716 KB Output is correct
12 Correct 58 ms 716 KB Output is correct
13 Correct 83 ms 716 KB Output is correct
14 Correct 75 ms 716 KB Output is correct
15 Correct 80 ms 716 KB Output is correct
16 Correct 80 ms 716 KB Output is correct