oj.uz

Submission #242661

# Submission time Handle Problem Language Result Execution time Memory
242661 2020-06-28T18:21:32 Z vanic Zagonetka (COI18_zagonetka) C++14
18 / 100
 75 ms 896 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];
set < 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(set < int >::const_iterator it=ms[s][x].begin(); it!=ms[s][x].end(); it++){
		if(!bio[*it]){
			gazi(*it, s);
		}
	}
	if(s){
		q[x]=val.back();
		val.pop_back();
	}
}

vector < int > svi;


void rijesi(int x, bool s){
	for(set < int >::const_iterator it=ms[s][x].begin(); it!=ms[s][x].end(); it++){
		if(!q[*it]){
			rijesi(*it, 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";
			for(set < int >::const_iterator it=ms[1][pos[j]].begin(); it!=ms[1][pos[j]].end(); it++){
				val.push_back(p[*it]);
			}
			for(set < int >::const_iterator it=ms[0][pos[j+i]].begin(); it!=ms[0][pos[j+i]].end(); it++){
				val.push_back(p[*it]);
			}
			val.push_back(p[pos[i+j]]);
			val.push_back(p[pos[j]]);
			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]].insert(pos[j+i]);
				for(set < int >::const_iterator it=ms[1][pos[j+i]].begin(); it!=ms[1][pos[j+i]].end(); it++){
					ms[1][pos[j]].insert(*it);
				}
				ms[0][pos[j+i]].insert(pos[j]);
				for(set < int >::const_iterator it=ms[0][pos[j]].begin(); it!=ms[0][pos[j]].end(); it++){
					ms[0][pos[j+i]].insert(*it);
				}
			}
		}
	}
	cout << "end\n";
	for(int i=0; i<n; i++){
		svi.push_back(i+1);
		q[i]=0;
	}
	int sz;
	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

zagonetka.cpp: In function 'int main()':
zagonetka.cpp:98:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=1; j<val.size(); j++){
                 ~^~~~~~~~~~~
zagonetka.cpp:138:6: warning: unused variable 'sz' [-Wunused-variable]
  int sz;
      ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 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 Runtime error 7 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 384 KB Output is correct
2 Correct 28 ms 384 KB Output is correct
3 Correct 28 ms 384 KB Output is correct
4 Correct 37 ms 384 KB Output is correct
5 Correct 13 ms 384 KB Output is correct
6 Correct 33 ms 384 KB Output is correct
7 Correct 9 ms 384 KB Output is correct
8 Correct 10 ms 384 KB Output is correct
9 Correct 21 ms 384 KB Output is correct
10 Correct 16 ms 384 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Runtime error 7 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 384 KB Output is correct
2 Correct 75 ms 384 KB Output is correct
3 Correct 64 ms 384 KB Output is correct
4 Correct 38 ms 768 KB Output is correct
5 Correct 52 ms 768 KB Output is correct
6 Correct 54 ms 896 KB Output is correct
7 Runtime error 9 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -