Submission #45161

#	Time	Username	Problem	Language	Result	Execution time	Memory
45161		reality	Library (JOI18_library)	C++17	100 / 100	657 ms	716 KiB

library

#include "library.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

const int N = (int)(1e6) + 5;

int was[N];

int get(int node,int n) {
	vi cnt;
	for (int i = 0;i < n;++i)
		if (!was[i])
			cnt.pb(i);
	while (cnt.size() != 1) {
		int sz = cnt.size() / 2;
		vi lf,rg;
		for (int i = 0;i < cnt.size();++i)
			if (i < sz)
				lf.pb(cnt[i]);
			else
				rg.pb(cnt[i]);
		vi cur(n,0);
		for (auto it : lf)
			cur[it] = 1;
		int s1 = Query(cur);
		cur[node] = 1;
		int s2 = Query(cur);
		if (s1 == s2)
			cnt = lf;
		else
			cnt = rg;
	}
	return cnt.back();
}
void Solve(int N)
{
	if (N == 1) {
		Answer(vi{1});
		return;
	}
	if (N == 2) {
		Answer(vi{1,2});
		return;
	}
	vi answer;
	int root = -1;
	for (int i = 0;i < N;++i) {
		vi cnt;
		for (int j = 0;j < N;++j)
			if (j != i)
				cnt.pb(1);
			else
				cnt.pb(0);
		if (Query(cnt) == 1)
			root = i;
	}
	answer.pb(root + 1);
	was[root] = 1;
	for (int i = 1;i < N;++i) {
		int nxt = get(root,N);
		answer.pb(nxt + 1);
		root = nxt;
		was[root] = 1;
	}
	Answer(answer);
}

Compilation message (stderr)

library.cpp: In function 'int get(int, int)':
library.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0;i < cnt.size();++i)
                  ~~^~~~~~~~~~~~

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