oj.uz

답안 #630058

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
630058 2022-08-15T15:18:55 Z Arnch 도서관 (JOI18_library) C++17
0 / 100
 2000 ms 676 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;

	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();

			/*cout<<"&&**" <<endl;
			for(auto j : res) cout<<j <<' ';
			cout<<endl;
			for(auto j : vc[l]) cout<<j <<' ';
			cout<<"-----------------" <<endl;*/

			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;	
		}
	}

	/*for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(e[i][j]) {
				cout<<"^^" <<i <<' ' <<j <<endl;
			}*/

	vector<int> res;
	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(Sz(res) < n) {
		int u = res.back();
		for(int j = 1; j <= n; j++) {
			if(e[u][j] && !vis[j]) {
				res.push_back(j);
				vis[j] = 1;
				break;
			}
		}
	}

	Answer(res);

}

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3003 ms 676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3003 ms 676 KB Time limit exceeded
2 Halted 0 ms 0 KB -