oj.uz

답안 #242657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242657 2020-06-28T16:42:02 Z vanic Zagonetka (COI18_zagonetka) C++14
18 / 100
 3000 ms 263156 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>

using namespace std;

const int maxn=105;

int p[maxn];
int q[maxn];
int pos[maxn];
vector < int > ms[2][maxn];
vector < int > val;

void siri(int x, bool s){
	val.push_back(p[x]);
	for(int i=0; i<ms[s][x].size(); i++){
		siri(ms[s][x][i], s);
	}
}

void siri2(int x, bool s){
	val.push_back(x);
	for(int i=0; i<ms[s][x].size(); i++){
		if(!q[ms[s][x][i]]){
			siri2(ms[s][x][i], s);
		}
	}
}

void gazi(int x, bool s){
	if(!s){
		q[x]=val.back();
		val.pop_back();
	}
	for(int i=0; i<ms[s][x].size(); 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++){
			siri(pos[j], 1);
			siri(pos[j+i], 0);
			sort(val.begin(), val.end());
			for(int k=0; k<n; k++){
				q[k]=p[k];
			}
			gazi(pos[j], 1);
			gazi(pos[j+i], 0);
			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);
			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);
			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:20: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:27: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:39: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:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0; j<val.size(); j++){
                  ~^~~~~~~~~~~
zagonetka.cpp:99:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k=0; k<ms[0][val[j]].size(); k++){
                   ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:127:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0; j<val.size(); j++){
                  ~^~~~~~~~~~~
zagonetka.cpp:129:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k=0; k<ms[1][val[j]].size(); k++){
                   ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:88:6: warning: unused variable 'br' [-Wunused-variable]
  int br;
      ^~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB not a permutation
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 384 KB Output is correct
2 Correct 36 ms 384 KB Output is correct
3 Correct 31 ms 384 KB Output is correct
4 Correct 43 ms 384 KB Output is correct
5 Correct 15 ms 384 KB Output is correct
6 Correct 38 ms 384 KB Output is correct
7 Correct 10 ms 384 KB Output is correct
8 Correct 10 ms 384 KB Output is correct
9 Correct 24 ms 404 KB Output is correct
10 Correct 21 ms 384 KB Output is correct

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 384 KB Output is correct
2 Runtime error 197 ms 1952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 384 KB Output is correct
2 Correct 79 ms 384 KB Output is correct
3 Correct 78 ms 384 KB Output is correct
4 Execution timed out 3102 ms 263156 KB Time limit exceeded
5 Halted 0 ms 0 KB -