oj.uz

Submission #242659

# Submission time Handle Problem Language Result Execution time Memory
242659 2020-06-28T17:15:00 Z vanic Zagonetka (COI18_zagonetka) C++14
18 / 100
 80 ms 504 KB 
#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];
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;
	if(!s){
		q[x]=val.back();
		val.pop_back();
	}
	for(int i=0; i<ms[s][x].size(); i++){
		if(!bio[ms[s][x][i]]){
			gazi(ms[s][x][i], s);
		}
	}
	if(s){
		q[x]=val.back();
		val.pop_back();
	}
}

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);
			bio.reset();
//			cout << "na manje\n";
			siri(pos[j+i], 0);
			bio.reset();
			sort(val.begin(), val.end());
			prov=1;
//			cout << val.size() << '\n';
			for(int j=1; j<val.size(); j++){
				if(val[j]==val[j-1]){
					prov=0;
					val.clear();
					break;
				}
			}
			if(prov){
				for(int k=0; k<n; k++){
					q[k]=p[k];
				}
				gazi(pos[j], 1);
				bio.reset();
				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]);
				ms[0][pos[j+i]].push_back(pos[j]);
			}
		}
	}
	cout << "end\n";
	vector < int > svi;
	for(int i=0; i<n; i++){
		svi.push_back(i+1);
		q[i]=0;
	}
	int br;
	int sz;
	set < int >::const_iterator it;
	for(int i=0; i<n; i++){
		if(!q[i]){
			siri2(i, 0);
			bio.reset();
			sort(val.begin(), val.end());
			sz=val.size();
			for(int xx=0; xx<sz; xx++){
				for(int j=0; j<val.size(); j++){
					prov=1;
					for(int k=0; k<ms[0][val[j]].size(); k++){
						if(!q[ms[0][val[j]][k]]){
							prov=0;
							break;
						}
					}
					if(prov){
						q[val[j]]=svi[0];
						svi.erase(svi.begin());
						val.erase(val.begin()+j);
						break;
					}
				}
			}
		}
		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]){
			siri2(i, 1);
			bio.reset();
			sort(val.begin(), val.end());
			sz=val.size();
			for(int xx=0; xx<sz; xx++){
				for(int j=0; j<val.size(); j++){
					prov=1;
					for(int k=0; k<ms[1][val[j]].size(); k++){
						if(!q[ms[1][val[j]][k]]){
							prov=0;
							break;
						}
					}
					if(prov){
						q[val[j]]=svi[0];
						svi.erase(svi.begin());
						val.erase(val.begin()+j);
						break;
					}
				}
			}
		}
		cout << q[i] << " ";
	}
	cout << '\n';
	cout.flush();
	return 0;
}

Compilation message

zagonetka.cpp: In function 'void siri(int, bool)':
zagonetka.cpp:24: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 siri2(int, bool)':
zagonetka.cpp:34: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 gazi(int, bool)':
zagonetka.cpp:47: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:80:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=1; j<val.size(); j++){
                 ~^~~~~~~~~~~
zagonetka.cpp:125:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0; j<val.size(); j++){
                  ~^~~~~~~~~~~
zagonetka.cpp:127:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k=0; k<ms[0][val[j]].size(); k++){
                   ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:156:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0; j<val.size(); j++){
                  ~^~~~~~~~~~~
zagonetka.cpp:158:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k=0; k<ms[1][val[j]].size(); k++){
                   ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:115:6: warning: unused variable 'br' [-Wunused-variable]
  int br;
      ^~

Subtask #1
0 / 9.0

# 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 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Incorrect 4 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 384 KB Output is correct
2 Correct 32 ms 384 KB Output is correct
3 Correct 31 ms 384 KB Output is correct
4 Correct 34 ms 384 KB Output is correct
5 Correct 13 ms 384 KB Output is correct
6 Correct 35 ms 384 KB Output is correct
7 Correct 11 ms 384 KB Output is correct
8 Correct 11 ms 384 KB Output is correct
9 Correct 29 ms 384 KB Output is correct
10 Correct 17 ms 384 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 384 KB Output is correct
2 Correct 76 ms 384 KB Output is correct
3 Correct 62 ms 384 KB Output is correct
4 Correct 37 ms 504 KB Output is correct
5 Correct 49 ms 504 KB Output is correct
6 Correct 49 ms 384 KB Output is correct
7 Correct 40 ms 384 KB Output is correct
8 Correct 49 ms 384 KB Output is correct
9 Correct 53 ms 384 KB Output is correct
10 Correct 73 ms 384 KB Output is correct
11 Correct 64 ms 384 KB Output is correct
12 Correct 60 ms 384 KB Output is correct
13 Incorrect 80 ms 504 KB Output isn't correct
14 Halted 0 ms 0 KB -