oj.uz

답안 #245168

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
245168 2020-07-05T16:13:18 Z vanic Zagonetka (COI18_zagonetka) C++14
100 / 100
 95 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;
}

bool cmp1(int a, int b){
	return p[a]>p[b];
}

bool cmp2(int a, int b){
	return p[a]<p[b];
}

void gazi(int x, bool s, int gran){
	if(s){
		sort(ms[s][x].begin(), ms[s][x].end(), cmp1);
	}
	else{
		sort(ms[s][x].begin(), ms[s][x].end(), cmp2);
	}
	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==9){
				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:59: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:76: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:101:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0; k<ms[1][pos[j]].size(); k++){
                 ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:106: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:143:18: 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 k=0; k<ms[1][pos[j+i]].size(); k++){
                 ~^~~~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:153:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int l=0; l<ms[0][pos[j]].size(); l++){
                   ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:163: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:169:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0; k<ms[0][pos[j]].size(); k++){
                 ~^~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:173:20: 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.0 / 9.0

# 결과 실행 시간 메모리 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 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 384 KB Output is correct
2 Correct 26 ms 384 KB Output is correct
3 Correct 36 ms 384 KB Output is correct
4 Correct 44 ms 384 KB Output is correct
5 Correct 16 ms 384 KB Output is correct
6 Correct 35 ms 384 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 11 ms 384 KB Output is correct
9 Correct 39 ms 384 KB Output is correct
10 Correct 20 ms 384 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 11 ms 384 KB Output is correct
4 Correct 11 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 9 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 12 ms 384 KB Output is correct
9 Correct 9 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 10 ms 384 KB Output is correct
12 Correct 9 ms 384 KB Output is correct

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 384 KB Output is correct
2 Correct 95 ms 384 KB Output is correct
3 Correct 63 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 8 ms 384 KB Output is correct
7 Correct 23 ms 384 KB Output is correct
8 Correct 38 ms 384 KB Output is correct
9 Correct 30 ms 504 KB Output is correct
10 Correct 78 ms 504 KB Output is correct
11 Correct 78 ms 384 KB Output is correct
12 Correct 81 ms 384 KB Output is correct
13 Correct 76 ms 384 KB Output is correct
14 Correct 66 ms 384 KB Output is correct
15 Correct 91 ms 384 KB Output is correct
16 Correct 84 ms 384 KB Output is correct