Submission #267226

#	Time	Username	Problem	Language	Result	Execution time	Memory
267226		Shisuko	도서관 (JOI18_library)	C++14	19 / 100	3027 ms	20556 KiB

library

#include <cstdio>
#include <chrono>
#include <random>
#include <algorithm>
#include <vector>
#include <set>
#include <iostream>
#include "library.h"
using namespace std;

void Solve(int N)
{
	if(N==1)
	{
		Answer({1});
		return;
	}
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	vector<int> M(N,0);

	vector<vector<int>> adj(N);
	set<pair<int,int>> done;
	int links = 0;
	while(links < N-1)
	{
		int x = uniform_int_distribution<int>(0,N-2)(rng);
		int y = uniform_int_distribution<int>(x+1,N-1)(rng);
		if(done.find({x,y})==done.end())
		{
			done.insert({x,y});
			M[x] = M[y] = 1;
			if(Query(M)==1)
			{
				adj[x].push_back(y);
				adj[y].push_back(x);
				links++;
			}
			M[x] = M[y] = 0;
		}
	}
	vector<int> res(N);
	for(int g = 0; g < N; g++)
		if(adj[g].size()==1)
		{
			res[0] = g;
			break;
		}
		
	for(int i = 1; i < N; i++)
	{
		for(const int& g : adj[res[i-1]])
			if(i==1 || g!=res[i-2])
				res[i] = g;
	}
	for(int& g : res)
		++g;
	Answer(res);
}

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