Submission #245168

#	Time	Username	Problem	Language	Result	Execution time	Memory
245168		vanic	Zagonetka (COI18_zagonetka)	C++14	100 / 100	95 ms	504 KiB

zagonetka

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <bitset>
#include <assert.h>

using namespace std;

const int maxn=105;

int p[maxn];
int q[maxn];
int pos[maxn];
vector < int > ms[2][maxn];
bitset < maxn > imam[2][maxn];
bitset < maxn > bio;
vector < int > val;
vector < pair < int, int > > query;

pair < int, int > uvjet[maxn];
int m;
int n;

void precompute(){
	cin >> m;
	for(int i=0; i<m; i++){
		cin >> uvjet[i].first >> uvjet[i].second;
		uvjet[i].first--;
		uvjet[i].second--;
	}
}

bool provjeri(){
	for(int i=0; i<m; i++){
		if(q[uvjet[i].first]>q[uvjet[i].second]){
			return 0;
		}
	}
	return 1;
}

bool cmp1(int a, int b){
	return p[a]>p[b];
}

bool cmp2(int a, int b){
	return p[a]<p[b];
}

void gazi(int x, bool s, int gran){
	if(s){
		sort(ms[s][x].begin(), ms[s][x].end(), cmp1);
	}
	else{
		sort(ms[s][x].begin(), ms[s][x].end(), cmp2);
	}
	bio[x]=1;
	for(int i=0; i<ms[s][x].size(); i++){
		if(s && gran<p[ms[s][x][i]]){
			continue;
		}
		else if(!s && gran>p[ms[s][x][i]]){
			continue;
		}
		if(!bio[ms[s][x][i]]){
			gazi(ms[s][x][i], s, gran);
		}
	}
	q[x]=val.back();
	val.pop_back();
}

void rijesi(int x, bool s){
	sort(ms[s][x].begin(), ms[s][x].end());
	for(int i=0; i<ms[s][x].size(); i++){
		if(!q[ms[s][x][i]]){
			rijesi(ms[s][x][i], s);
		}
	}
	q[x]=val.back();
	val.pop_back();
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> p[i];
		pos[p[i]]=i;
	}
//	precompute(); //test
	bool prov;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n-i; j++){
			if(imam[1][pos[j]][pos[j+i]]){
				continue;
			}
			for(int k=0; k<ms[1][pos[j]].size(); k++){
				if(p[ms[1][pos[j]][k]]<j+i){
					val.push_back(p[ms[1][pos[j]][k]]);
				}
			}
			for(int k=0; k<ms[0][pos[j+i]].size(); k++){
				if(p[ms[0][pos[j+i]][k]]>j){
					val.push_back(p[ms[0][pos[j+i]][k]]);
				}
			}
			val.push_back(j);
			val.push_back(j+i);
			sort(val.begin(), val.end());
			for(int k=0; k<n; k++){
				q[k]=p[k];
			}
			gazi(pos[j], 1, j+i);
			reverse(val.begin(), val.end());
			gazi(pos[j+i], 0, j);
			bio.reset();
			cout << "query ";
			for(int i=0; i<n; i++){
				cout << q[i] << " ";
			}
			cout << '\n';
			cout.flush();
			cin >> prov;
//			prov=provjeri(); //test
			if(prov){
				continue;
			}
//			cout << "nasao " << pos[j]+1 << " " << pos[j+i]+1 << '\n';
/*			if(j==2 && j+i==9){
				cout << "problem\n";
				cout << ms[1][pos[j]].size() << " " << ms[0][pos[j+i]].size() << '\n';
				for(int i=0; i<n; i++){
					cout << q[i] << " ";
				}
				cout << '\n';
			}*/
			ms[1][pos[j]].push_back(pos[j+i]);
			imam[1][pos[j]][pos[j+i]]=1;
			for(int l=0; l<ms[0][pos[j]].size(); l++){
				if(!imam[1][ms[0][pos[j]][l]][pos[j+i]]){
					ms[1][ms[0][pos[j]][l]].push_back(pos[j+i]);
					imam[1][ms[0][pos[j]][l]][pos[j+i]]=1;
				}
			}
			for(int k=0; k<ms[1][pos[j+i]].size(); k++){
				if(!imam[1][pos[j]][ms[1][pos[j+i]][k]]){
					ms[1][pos[j]].push_back(ms[1][pos[j+i]][k]);
					imam[1][pos[j]][ms[1][pos[j+i]][k]]=1;
					for(int l=0; l<ms[0][pos[j]].size(); l++){
						if(!imam[1][ms[0][pos[j]][l]][ms[1][pos[j+i]][k]]){
							ms[1][ms[0][pos[j]][l]].push_back(ms[1][pos[j+i]][k]);
							imam[1][ms[0][pos[j]][l]][ms[1][pos[j+i]][k]]=1;
						}
					}
				}
			}
			ms[0][pos[j+i]].push_back(pos[j]);
			imam[0][pos[j+i]][pos[j]]=1;
			for(int l=0; l<ms[1][pos[j+i]].size(); l++){
				if(!imam[0][ms[1][pos[j+i]][l]][pos[j]]){
					ms[0][ms[1][pos[j+i]][l]].push_back(pos[j]);
					imam[0][ms[1][pos[j+i]][l]][pos[j]]=1;
				}
			}
			for(int k=0; k<ms[0][pos[j]].size(); k++){
				if(!imam[0][pos[j+i]][ms[0][pos[j]][k]]){
					ms[0][pos[j+i]].push_back(ms[0][pos[j]][k]);
					imam[0][pos[j+i]][ms[0][pos[j]][k]]=1;
					for(int l=0; l<ms[1][pos[j+i]].size(); l++){
						if(!imam[0][ms[1][pos[j+i]][l]][ms[0][pos[j]][k]]){
							ms[0][ms[1][pos[j+i]][l]].push_back(ms[0][pos[j]][k]);
							imam[0][ms[1][pos[j+i]][l]][ms[0][pos[j]][k]]=1;
						}
					}
				}
			}
		}
	}
	cout << "end\n";
	for(int i=0; i<n; i++){
		val.push_back(n-i);
		q[i]=0;
	}
	for(int i=0; i<n; i++){
		if(!q[i]){
			rijesi(i, 0);
		}
		cout << q[i] << " ";
	}
	cout << '\n';
	for(int i=0; i<n; i++){
		val.push_back(i+1);
		q[i]=0;
	}
/*	for(int i=0; i<n; i++){
		cout << "na " << i << '\n';
		for(int j=0; j<ms[1][i].size(); j++){
			cout << ms[1][i][j] << " ";
		}
		cout << '\n';
	}*/
	for(int i=0; i<n; i++){
		if(!q[i]){
			rijesi(i, 1);
		}
		cout << q[i] << " ";
	}
	cout << '\n';
	cout.flush();
	return 0;
}

Compilation message (stderr)

zagonetka.cpp: In function 'void gazi(int, bool, int)':
zagonetka.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[s][x].size(); i++){
               ~^~~~~~~~~~~~~~~~
zagonetka.cpp: In function 'void rijesi(int, bool)':
zagonetka.cpp:76:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[s][x].size(); i++){
               ~^~~~~~~~~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:101:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0; k<ms[1][pos[j]].size(); k++){
                 ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:106:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0; k<ms[0][pos[j+i]].size(); k++){
                 ~^~~~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:143:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int l=0; l<ms[0][pos[j]].size(); l++){
                 ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:149:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0; k<ms[1][pos[j+i]].size(); k++){
                 ~^~~~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:153:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int l=0; l<ms[0][pos[j]].size(); l++){
                   ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:163:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int l=0; l<ms[1][pos[j+i]].size(); l++){
                 ~^~~~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:169:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0; k<ms[0][pos[j]].size(); k++){
                 ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:173:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int l=0; l<ms[1][pos[j+i]].size(); l++){
                   ~^~~~~~~~~~~~~~~~~~~~~~~

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