oj.uz

답안 #503627

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
503627 2022-01-08T13:10:18 Z fatemetmhr 도서관 (JOI18_library) C++17
100 / 100
 428 ms 508 KB 
//  ~Be name khoda~  //

#include<bits/stdc++.h>
#include "library.h"

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn  =  1e6   + 10;
const int maxn5 =  2e3   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;

int per[maxn5];
vector <int> av, as, part, out, adj[maxn5];
bool mark[maxn5];
int cnt = 0;
bool done = false;

inline int found_adj(){
	int e = 0;
	for(auto u : as) for(auto v : adj[u]){
		e += out[v - 1];
		//cout << u << ' ';
	}
	e /= 2;
	//cout << " final " << e << endl;
	return int(as.size()) - e;
}

inline bool ask(){
	cnt++;
	if(cnt > 20000){
		done = true;
		return false;
	}
	for(int i = 0; i < out.size(); i++)
		out[i] = 0;
	for(auto u : as)
		out[u - 1] = 1;
	int ans = Query(out);
	return ans < found_adj();
}

inline void parti(){
	if(done) return;
	for(int i = 0; i < av.size(); i++)
		per[i] = i;
	shuffle(per, per + av.size(), rng);
	as.clear();
	for(int i = 0; i < av.size(); i++)
		if(per[i] <= (av.size() - 1) / 2)
			as.pb(av[i]);
	bool re = ask();
	if(re){
		part.clear();
		for(auto u : as)
			part.pb(u);
		return; 
	}
	if(done) return;
	//*
	as.clear();
	for(int i = 0; i < av.size(); i++)
		if(per[i] > (av.size() - 1) / 2)
			as.pb(av[i]);
	re = ask();
	if(re){
		part.clear();
		for(auto u : as)
			part.pb(u);
		return; 
	}
	//*/
	parti();
	return;
}

inline pair<int, int> find_adj(){
	if(av.size() == 2) return {av[0], av[1]};
	if(av.size() == 3){
		as.clear();
		as.pb(av[0]);
		as.pb(av[1]);
		bool re = ask();
		if(re) return {av[0], av[1]};
		as.pop_back();
		as.pb(av[2]);
		re = ask();
		if(re) return {av[0], av[2]};
		return {av[1], av[2]};
	}
	parti();
	if(done) return {0, 0};
	av.clear();
	for(auto u : part)
		av.pb(u);
	return find_adj();
}

void Solve(int n)
{
	if(n == 1){
		vector <int> ans;
		ans.pb(1);
		Answer(ans);
		return;
	}
	out.resize(n);
	int rem = n - 1;
	while(rem){
		av.clear();
		for(int i = 1; i <= n; i++) if(adj[i].size() < 2)
			av.pb(i);
		pair <int, int> tmp = find_adj();
		if(done) return;
		adj[tmp.fi].pb(tmp.se);
		adj[tmp.se].pb(tmp.fi);
		//cout << "found out " << tmp.fi << ' ' << tmp.se << " adj " << endl;
		rem--;
	}
	vector <int> ans;
	int v = -1;
	for(int i = 1; i <= n; i++) if(adj[i].size() == 1)
		v = i;
	ans.pb(v);
	mark[v] = true;
	v = adj[v][0];
	while(true){
		ans.pb(v);
		mark[v] = true;
		if(adj[v].size() == 1)
			break;
		int u = adj[v][0];
		if(mark[u])
			u = adj[v][1];
		v = u;
	}
	Answer(ans);
	return;
}

Compilation message

library.cpp: In function 'bool ask()':
library.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i = 0; i < out.size(); i++)
      |                 ~~^~~~~~~~~~~~
library.cpp: In function 'void parti()':
library.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(int i = 0; i < av.size(); i++)
      |                 ~~^~~~~~~~~~~
library.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i = 0; i < av.size(); i++)
      |                 ~~^~~~~~~~~~~
library.cpp:65:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   if(per[i] <= (av.size() - 1) / 2)
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
library.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i = 0; i < av.size(); i++)
      |                 ~~^~~~~~~~~~~
library.cpp:78:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   if(per[i] > (av.size() - 1) / 2)
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 328 KB # of queries: 2646
2 Correct 36 ms 356 KB # of queries: 2494
3 Correct 37 ms 328 KB # of queries: 2886
4 Correct 34 ms 352 KB # of queries: 2759
5 Correct 38 ms 340 KB # of queries: 2841
6 Correct 43 ms 340 KB # of queries: 2772
7 Correct 47 ms 360 KB # of queries: 2841
8 Correct 49 ms 336 KB # of queries: 2686
9 Correct 39 ms 344 KB # of queries: 2746
10 Correct 23 ms 328 KB # of queries: 1717
11 Correct 0 ms 328 KB # of queries: 0
12 Correct 0 ms 328 KB # of queries: 0
13 Correct 0 ms 328 KB # of queries: 3
14 Correct 0 ms 328 KB # of queries: 4
15 Correct 2 ms 328 KB # of queries: 92
16 Correct 3 ms 328 KB # of queries: 208

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 328 KB # of queries: 2646
2 Correct 36 ms 356 KB # of queries: 2494
3 Correct 37 ms 328 KB # of queries: 2886
4 Correct 34 ms 352 KB # of queries: 2759
5 Correct 38 ms 340 KB # of queries: 2841
6 Correct 43 ms 340 KB # of queries: 2772
7 Correct 47 ms 360 KB # of queries: 2841
8 Correct 49 ms 336 KB # of queries: 2686
9 Correct 39 ms 344 KB # of queries: 2746
10 Correct 23 ms 328 KB # of queries: 1717
11 Correct 0 ms 328 KB # of queries: 0
12 Correct 0 ms 328 KB # of queries: 0
13 Correct 0 ms 328 KB # of queries: 3
14 Correct 0 ms 328 KB # of queries: 4
15 Correct 2 ms 328 KB # of queries: 92
16 Correct 3 ms 328 KB # of queries: 208
17 Correct 428 ms 376 KB # of queries: 19719
18 Correct 387 ms 500 KB # of queries: 19581
19 Correct 401 ms 496 KB # of queries: 19139
20 Correct 366 ms 492 KB # of queries: 18313
21 Correct 329 ms 488 KB # of queries: 17132
22 Correct 385 ms 504 KB # of queries: 19743
23 Correct 355 ms 492 KB # of queries: 19837
24 Correct 142 ms 356 KB # of queries: 8972
25 Correct 334 ms 508 KB # of queries: 19697
26 Correct 357 ms 372 KB # of queries: 18008
27 Correct 137 ms 364 KB # of queries: 9063
28 Correct 315 ms 488 KB # of queries: 19785
29 Correct 370 ms 484 KB # of queries: 19675
30 Correct 375 ms 500 KB # of queries: 19580