oj.uz

Submission #630063

# Submission time Handle Problem Language Result Execution time Memory
630063 2022-08-15T15:28:02 Z Arnch Library (JOI18_library) C++17
0 / 100
 21 ms 556 KB 
#include<bits/stdc++.h>
#include "library.h"
using namespace std;

/*
	Query(vector<int> &m);
	Answer(vector<int> &res);
*/

#define Sz(x) (int)(x.size())
#define All(x) (x).begin(), (x).end()

const int N = 1e3 + 10;

bool mark[N], vis[N];
int e[N][N];

int Ask(vector<int> &ask) {
	for(int i = 1; i <= Sz(ask); i++) ask[i - 1] = mark[i];
	return Query(ask);
}

void Solve(int N) {
	int n = N;

	if(n == 1) {
		vector<int> ans = {1};
		Answer(ans);
		return;
	}

	vector<vector<int> > vc;
	
	vector<int> ask(N);

	for(int i = 1; i <= n; i++) {
		vc.push_back({i});
		while(true) {
			for(auto j : vc) 
				for(auto x : j) mark[x] = 1;

			int t = Ask(ask);
			if(t == Sz(vc)) break;

			for(auto j : vc)
				for(auto x : j) mark[x] = 0;


			vector<int> res = vc.back(); vc.pop_back();

			for(auto j : res) mark[j] = 1;
			int l = 0, r = Sz(vc);
			while(r - l > 1) {
				int mid = (l + r) >> 1;
				for(int i = l; i < mid; i++) {
					for(auto j : vc[i]) mark[j] = 1;
				}
				t = Ask(ask);

				for(int i = l; i < mid; i++) {
					for(auto j : vc[i]) mark[j] = 0;
				}

				if(t != mid - l + 1) r = mid;
				else l = mid;
			}
			for(auto j : res) mark[j] = 0;

			int u1 = res[0], u2 = res.back();
			int v1 = vc[l][0], v2 = vc[l].back();

			mark[u1] = mark[v1] = 1;
			t = Ask(ask);
			if(t == 1) {
				e[u1][v1] = e[v1][u1] = 1;
				mark[u1] = mark[v1] = 0;
		
				reverse(All(vc[l]));
				for(auto j : res) vc[l].push_back(j);
				res.clear();
		
				continue;
			}
			mark[u1] = mark[v1] = 0;
			
			mark[u1] = mark[v2] = 1;
			t = Ask(ask);
			if(t == 1) {
				e[u1][v2] = e[v2][u1] = 1;
				mark[u1] = mark[v2] = 0;

				for(auto j : res) vc[l].push_back(j);
				res.clear();

				continue;
			}
			mark[u1] = mark[v2] = 0;

			mark[u2] = mark[v1] = 1;
			t = Ask(ask);
			if(t == 1) {
				e[u2][v1] = e[v1][u2] = 1;
				mark[u2] = mark[v1] = 0;
		
				for(auto j : vc[l]) res.push_back(j);
				vc[l].swap(res);
				res.clear();

				continue;
			}
			mark[u2] = mark[v1] = 0;
			
			mark[u2] = mark[v2] = 1;
			t = Ask(ask);
			if(t == 1) {
				e[u2][v2] = e[v2][u2] = 1;
				mark[u2] = mark[v2] = 0;
		
				reverse(All(res));
				for(auto j : res) vc[l].push_back(j);
				res.clear();

				continue;
			}
			mark[u2] = mark[v2] = 0;	
		}
	}

	vector<int> res, ans;
	int u;
	for(int i = 1; i <= n; i++) {
		int cnt = 0;
		for(int j = 1; j <= n; j++) cnt += e[i][j];
		if(cnt == 1) {
			u = i;
			vis[u] = 1;
			break;
		}
	}
	res.push_back(u);
	while(!res.empty()) {
		int u = res.back();
		res.pop_back();
		ans.push_back(u);
		for(int j = 1; j <= n; j++) {
			if(e[u][j] && !vis[j]) {
				res.push_back(j);
				vis[j] = 1;
				break;
			}
		}
	}

	Answer(ans);

}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 556 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 556 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -