oj.uz

답안 #940618

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
940618 2024-03-07T11:47:25 Z WonderfulWhale 도서관 (JOI18_library) C++17
0 / 100
 9 ms 692 KB 
#include<bits/stdc++.h>
#include"library.h"
using namespace std;

#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N;

vector<vector<int>> V;

bool f(vector<int> v, int X, int exl=-1) {
	vector<int> q(N, 0);
	q[X] = 1;
	bool skip = false;
	for(int x:v) {
		if(x==exl) {
			skip = true;
			continue;
		}
		for(int y:V[x])
			q[y] = 1;
	}
	//cerr << "we want to achieve: " << sz(v)-skip << "\n";
	return Query(q)==sz(v)-skip;
}

int Find(vector<int> v, int X, int exl=-1) {
	//cerr << "Find ";
	//for(int x:v) cerr << x << " ";
	//cerr << "\n";
	if(sz(v)==1)
		return v[0];
	vector<int> v1, v2;
	for(int i=0;i<sz(v);i++) {
		if(i%2==0) v1.pb(v[i]);
		else v2.pb(v[i]);
	}
	if(f(v1, X, exl)) {
		//cerr << "going v1\n";
		return Find(v1, X, exl);
	} else {
		//cerr << "going v2\n";
		return Find(v2, X, exl);
	}
}

void Solve(int n) {	
	N = n;
	V.pb({0});
	for(int i=1;i<n;i++) {
		vector<int> q(N, 0);
		for(auto x:V)
			for(auto y:x)
				q[y] = 1;
		q[i] = 1;
		int x = Query(q)-sz(V);
		if(x==1) {
			//cerr << "new\n";
			V.pb({i});
		} else if(x==0) {
			//cerr << "glue\n";
			vector<int> v(sz(V));
			iota(all(v), 0);
			int y = Find(v, i);
			vector<int> q1(N, 0);
			q1[i] = 1;
			q1[V[y][0]] = 1;
			if(Query(q1)==1) reverse(all(V[y]));
			V[y].pb(i);
		} else {
			//cerr << "merge\n";
			vector<int> v(sz(V));
			iota(all(v), 0);
			int a = Find(v, i);
			//cerr << "found: " << a << "\n";
			int b = Find(v, i, a);
			//cerr << "found: " << b << "\n";
			vector<int> q1(N, 0);
			q1[i] = 1;
			q1[V[a][0]] = 1;
			if(Query(q1)==1) reverse(all(V[a]));
			vector<int> q2(N, 0);
			q2[i] = 1;
			q2[V[b].back()] = 1;
			if(Query(q2)==1) reverse(all(V[b]));
			V.emplace_back();
			for(int x:V[a]) V.back().pb(x);
			V.back().pb(i);
			for(int x:V[b]) V.back().pb(x);
			swap(V[a], V.back());
			V.pop_back();
			swap(V[b], V.back());
			V.pop_back();
		}
	}
	vector<int> res;
	for(int x:V[0])
		res.pb(x+1);
	Answer(res);
}

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 692 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 692 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -