Submission #244287

# Submission time Handle Problem Language Result Execution time Memory
244287 2020-07-03T14:00:50 Z vanic Zagonetka (COI18_zagonetka) C++14
78 / 100
93 ms 504 KB
#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;
}

void gazi(int x, bool s, int gran){
	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==5){
				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

zagonetka.cpp: In function 'void gazi(int, bool, int)':
zagonetka.cpp:45: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:62: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:87:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0; k<ms[1][pos[j]].size(); k++){
                 ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:92: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:129:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int l=0; l<ms[0][pos[j]].size(); l++){
                 ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:135: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:139:20: 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 l=0; l<ms[1][pos[j+i]].size(); l++){
                 ~^~~~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:155:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0; k<ms[0][pos[j]].size(); k++){
                 ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:159:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int l=0; l<ms[1][pos[j+i]].size(); l++){
                   ~^~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 17 ms 384 KB Output is correct
2 Correct 34 ms 384 KB Output is correct
3 Correct 35 ms 384 KB Output is correct
4 Correct 32 ms 384 KB Output is correct
5 Correct 15 ms 384 KB Output is correct
6 Correct 42 ms 384 KB Output is correct
7 Correct 9 ms 384 KB Output is correct
8 Correct 14 ms 384 KB Output is correct
9 Correct 39 ms 384 KB Output is correct
10 Correct 22 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Incorrect 11 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 87 ms 384 KB Output is correct
2 Correct 93 ms 384 KB Output is correct
3 Correct 73 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 6 ms 416 KB Output is correct
7 Correct 18 ms 384 KB Output is correct
8 Correct 30 ms 384 KB Output is correct
9 Correct 26 ms 504 KB Output is correct
10 Correct 82 ms 384 KB Output is correct
11 Correct 65 ms 384 KB Output is correct
12 Correct 68 ms 384 KB Output is correct
13 Correct 74 ms 384 KB Output is correct
14 Correct 70 ms 504 KB Output is correct
15 Correct 76 ms 384 KB Output is correct
16 Correct 71 ms 384 KB Output is correct