Submission #970832

#	Time	Username	Problem	Language	Result	Execution time	Memory
970832		jcelin	Zagonetka (COI18_zagonetka)	C++14	9 / 100	170 ms	488 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];
int in[MAXN];
bool bio[MAXN];

bool query(){
	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] = 0;
	else brid[na][nb] = 2;
	
	return 1;
}


void najm(){
	set<int> s;
	topo.clear();
	vls.resize(n);
	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]++;
	}
	for(int i=1; i<=n; i++) if(in[i] == 0) s.insert(i);
	
	while(s.size()){
		int u = *s.begin();
		topo.PB(u);
		s.erase(u);
		for(auto &x : g[u]) if(--in[x] == 0) s.insert(x);
	}
	
	for(int i=0; i<n; i++) vls[topo[i] - 1] = i + 1;
	
	for(auto &x : vls) cout << x << " ";
	cout << endl;
}

void najv(){
	set<int> s;
	topo.clear();
	vls.resize(n);
	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]++;
	}
	for(int i=1; i<=n; i++) if(in[i] == 0) s.insert(i);
	
	while(s.size()){
		int u = *(--s.end());
		topo.PB(u);
		s.erase(u);
		for(auto &x : g[u]) if(--in[x] == 0) s.insert(x);
	}
	
	for(int i=0; i<n; i++) vls[topo[i] - 1] = i + 1;
	
	
	for(auto &x : vls) cout << x << " ";
	cout << endl;
}

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());
	cout << "end" << endl;
	najm();
	najv();
}


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

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