Submission #244245

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

zagonetka

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <bitset>

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];
vector < int > val;
bitset < maxn > bio;
/*
void siri(int x, bool s){
//	cout << "sirim " << x << endl;
	bio[x]=1;
	val.push_back(p[x]);
	for(int i=0; i<ms[s][x].size(); i++){
		if(!bio[ms[s][x][i]]){
			siri(ms[s][x][i], s);
		}
	}
}

void siri2(int x, bool s){
	bio[x]=1;
	val.push_back(x);
	for(int i=0; i<ms[s][x].size(); i++){
		if(!q[ms[s][x][i]] && !bio[ms[s][x][i]]){
			siri2(ms[s][x][i], s);
		}
	}
}
*/
void gazi(int x, bool s){
	bio[x]=1;
	for(int i=0; i<ms[s][x].size(); i++){
		if(!bio[ms[s][x][i]]){
			gazi(ms[s][x][i], s);
		}
	}
	q[x]=val.back();
	val.pop_back();
}

vector < int > svi;


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]=svi[0];
	svi.erase(svi.begin());
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> p[i];
		pos[p[i]]=i;
	}
	bool prov;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n-i; j++){
//			cout << "na vise\n";
//			siri(pos[j], 1);
//			cout << "na manje\n";
			prov=1;
			if(!imam[1][pos[j]][pos[j+i]]){
				for(int k=0; k<ms[1][pos[j]].size(); k++){
					val.push_back(p[ms[1][pos[j]][k]]);
				}
				for(int k=0; k<ms[0][pos[j+i]].size(); k++){
					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);
				bio.reset();
				reverse(val.begin(), val.end());
				gazi(pos[j+i], 0);
				bio.reset();
				cout << "query ";
				for(int k=0; k<n; k++){
					cout << q[k] << " ";
				}
				cout << '\n';
				cout.flush();
				cin >> prov;
			}
			if(!prov){
				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++){
		svi.push_back(i+1);
		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++){
		svi.push_back(n-i);
		q[i]=0;
	}
	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)':
zagonetka.cpp:44: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:58: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:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0; k<ms[1][pos[j]].size(); k++){
                  ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:88:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0; k<ms[0][pos[j+i]].size(); k++){
                  ~^~~~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:113:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int l=0; l<ms[0][pos[j]].size(); l++){
                  ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:119:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0; k<ms[1][pos[j+i]].size(); k++){
                  ~^~~~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:123:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int l=0; l<ms[0][pos[j]].size(); l++){
                    ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:133:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int l=0; l<ms[1][pos[j+i]].size(); l++){
                  ~^~~~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:139:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0; k<ms[0][pos[j]].size(); k++){
                  ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:143:21: 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: 0 / 22
• Subtask 4: 0 / 51