Submission #61696

#	Time	Username	Problem	Language	Result	Execution time	Memory
61696		cki86201	Library (JOI18_library)	C++11	100 / 100	873 ms	696 KiB

library

#include "library.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;

int Get(vector <int> &X, int N) {
	vector <int> M(N);
	rep(i, N) M[i] = 0;
	for(int e : X) M[e] = 1;
	return Query(M);
}

void Solve(int N)
{
	if(N == 1) {
		vector <int> res; res.pb(1);
		Answer(res);
		return;
	}
	vector<int> M(N);
	
	for(int i = 0; i < N; i++) {
		M[i] = 1;
	}
	int st = -1;
	rep(i, N) {
		M[i] = 0;
		if(Query(M) == 1) { st = i; break; }
		M[i] = 1;
	}
	int chk[1010] = {};
	chk[st] = 1;
	vector<int> res(N);
	res[0] = st;
	for(int i=1;i<N;i++) {
		vector <int> v;
		rep(j, N) if(chk[j] == 0) {
			v.pb(j);
		}
		int m = szz(v);
		if(m == 1) { res[i] = v[0]; continue; }
		int lg = 32 - __builtin_clz(m-1);
		int idx = 0;
		rep(j, lg) {
			vector <int> w;
			rep(k, m) if(1<<j & k) w.pb(v[k]);
			int v1 = Get(w, N);
			w.pb(res[i-1]);
			int v2 = Get(w, N);
			if(v1 == v2) idx |= 1<<j;
		}
		res[i] = v[idx];
		chk[v[idx]] = 1;
	}

	for(int i = 0; i < N; i++) {
		res[i] += 1;
	}

	Answer(res);
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81