oj.uz

답안 #267226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
267226 2020-08-16T01:51:35 Z Shisuko 도서관 (JOI18_library) C++14
19 / 100
 2000 ms 20556 KB 
#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.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 308 ms 1248 KB # of queries: 18320
2 Correct 296 ms 1224 KB # of queries: 18055
3 Correct 307 ms 1272 KB # of queries: 19611
4 Correct 354 ms 1400 KB # of queries: 19761
5 Correct 327 ms 1396 KB # of queries: 19826
6 Correct 296 ms 1392 KB # of queries: 19885
7 Correct 271 ms 1348 KB # of queries: 19795
8 Correct 364 ms 1144 KB # of queries: 18527
9 Correct 324 ms 1420 KB # of queries: 19696
10 Correct 155 ms 760 KB # of queries: 8249
11 Correct 0 ms 256 KB # of queries: 0
12 Correct 0 ms 256 KB # of queries: 1
13 Correct 0 ms 256 KB # of queries: 2
14 Correct 0 ms 256 KB # of queries: 4
15 Correct 2 ms 384 KB # of queries: 105
16 Correct 5 ms 392 KB # of queries: 345

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 308 ms 1248 KB # of queries: 18320
2 Correct 296 ms 1224 KB # of queries: 18055
3 Correct 307 ms 1272 KB # of queries: 19611
4 Correct 354 ms 1400 KB # of queries: 19761
5 Correct 327 ms 1396 KB # of queries: 19826
6 Correct 296 ms 1392 KB # of queries: 19885
7 Correct 271 ms 1348 KB # of queries: 19795
8 Correct 364 ms 1144 KB # of queries: 18527
9 Correct 324 ms 1420 KB # of queries: 19696
10 Correct 155 ms 760 KB # of queries: 8249
11 Correct 0 ms 256 KB # of queries: 0
12 Correct 0 ms 256 KB # of queries: 1
13 Correct 0 ms 256 KB # of queries: 2
14 Correct 0 ms 256 KB # of queries: 4
15 Correct 2 ms 384 KB # of queries: 105
16 Correct 5 ms 392 KB # of queries: 345
17 Execution timed out 3027 ms 20556 KB Time limit exceeded
18 Halted 0 ms 0 KB -