Submission #970851

#	Time	Username	Problem	Language	Result	Execution time	Memory
970851		jcelin	Zagonetka (COI18_zagonetka)	C++14	100 / 100	222 ms	744 KiB

zagonetka

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 107;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int brid[MAXN][MAXN], p[MAXN], n;
vi topo, vls, g[MAXN];
vii edg;
int in[MAXN];
bool bio[MAXN];

/*
14
10 13 9 1 5 6 7 4 12 11 14 3 8 2
3
13 10
6 2
4 5
*/

bool provjera(){
	for(auto &x : edg){
		if(vls[x.X] >= vls[x.Y]) return 0;
	}
	return 1;
}

bool query(){
	//return provjera();
	cout << "query ";
	for(auto &x : vls) cout << x << " ";
	cout << endl;
	
	bool x;
	cin >> x;
	return x;
}

void make_topo(){
	topo.clear();
	for(int i=1; i<=n; i++) g[i].clear(), in[i] = 0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++) if(brid[i][j]) g[i].PB(j), in[j]++;
	}
	
	vi s;
	for(int i=1; i<=n; i++) if(!in[i]) s.PB(i);
	
	while(s.size()){
		int u = s.back();
		topo.PB(u);
		s.PPB();
		for(auto &x : g[u]){
			if(--in[x] == 0) s.PB(x);
		}
	}
	
	
	vls.resize(n);
	for(int i=0; i<n; i++) vls[topo[i] - 1] = i + 1;
}

void dfs(int u){
	if(bio[u]) return;
	bio[u] = 1;
	for(int i=1; i<=n; i++) if(brid[u][i] == 2) dfs(i);
}

bool postoji(int x, int y){
	fill(bio, bio + n + 1, 0);
	dfs(x);
	return bio[y];
}

bool bridcheck(){
	make_topo();
	
	int na = 0, nb = 0;
	for(int i=n-1; i>=0; i--){
		if(na) break;
		for(int j=i; j<n; j++){
			if(na) break;
			int a = topo[i], b = topo[j];
			if(brid[a][b] != 1) continue;
			if(postoji(a, b)) brid[a][b] = 2;
			else na = a, nb = b;
		}
	}
	if(na == 0 and nb == 0) return 0;
	
	brid[na][nb] = 0;
	brid[nb][na] = 1;

	make_topo();
	
	brid[nb][na] = 0;
	if(!query()) brid[na][nb] = 2;
	else brid[na][nb] = 0;
	
	return 1;
}


int ans[MAXN];
void najm(set<int> pos, int lo, int hi){
	if(pos.empty()) return;
	int mini = *pos.begin();
	set<int> a;
	for(auto &x : g[mini]) if(pos.find(x) != pos.end()) a.insert(x);
	for(auto &x : a) pos.erase(x);
	
	if(a.empty()){
		pos.erase(mini);
		ans[mini] = lo;
		najm(pos, lo + 1, hi);
	}else{			
		najm(a, lo, lo + a.size() - 1);
		najm(pos, lo + a.size(), hi);	
	}
}

void najv(set<int> pos, int lo, int hi){
	if(pos.empty()) return;
	int mini = *pos.begin();
	set<int> a;
	for(auto &x : g[mini]) if(pos.find(x) != pos.end()) a.insert(x);
	for(auto &x : a) pos.erase(x);
	
	if(a.empty()){
		pos.erase(mini);
		ans[mini] = hi;
		najv(pos, lo, hi - 1);
	}else{			
		najv(a, hi - a.size() + 1, hi);
		najv(pos, lo, hi - a.size());	
	}
}

void solve(){
	cin >> n;
	for(int i=1; i<=n; i++) cin >> p[i];
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++) if(p[i] < p[j]) brid[i][j] = 1;
	}
	
	while(bridcheck());
	
	for(int i=1; i<=n; i++) g[i].clear();
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(brid[i][j]) g[j].PB(i);
		}
	}
	cout << "end" << endl;
	
	set<int> cur;
	for(int i=1; i<=n; i++) cur.insert(i);
	najm(cur, 1, n);
	for(int i=1; i<=n; i++) cout << ans[i] << " ";
	cout << "\n";
	
	
	for(int i=1; i<=n; i++) g[i].clear();
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(brid[i][j]) g[i].PB(j);
		}
	}
	najv(cur, 1, n);
	for(int i=1; i<=n; i++) cout << ans[i] << " ";
	cout << "\n";
}


int main(){
	solve();
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 51 / 51