oj.uz

답안 #503623

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
503623 2022-01-08T13:02:54 Z fatemetmhr 도서관 (JOI18_library) C++17
19 / 100
 431 ms 504 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;

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) exit(0);
	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(){
	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; 
	}
	//*
	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();
	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();
		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:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i = 0; i < out.size(); i++)
      |                 ~~^~~~~~~~~~~~
library.cpp: In function 'void parti()':
library.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i = 0; i < av.size(); i++)
      |                 ~~^~~~~~~~~~~
library.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 0; i < av.size(); i++)
      |                 ~~^~~~~~~~~~~
library.cpp:60:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   if(per[i] <= (av.size() - 1) / 2)
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
library.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i = 0; i < av.size(); i++)
      |                 ~~^~~~~~~~~~~
library.cpp:72:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   if(per[i] > (av.size() - 1) / 2)
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 328 KB # of queries: 2796
2 Correct 22 ms 356 KB # of queries: 2764
3 Correct 47 ms 328 KB # of queries: 2941
4 Correct 43 ms 328 KB # of queries: 2782
5 Correct 38 ms 360 KB # of queries: 2754
6 Correct 35 ms 352 KB # of queries: 2760
7 Correct 41 ms 328 KB # of queries: 2955
8 Correct 41 ms 468 KB # of queries: 2686
9 Correct 32 ms 340 KB # of queries: 2744
10 Correct 22 ms 328 KB # of queries: 1852
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: 5
15 Correct 3 ms 328 KB # of queries: 90
16 Correct 2 ms 328 KB # of queries: 165

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 328 KB # of queries: 2796
2 Correct 22 ms 356 KB # of queries: 2764
3 Correct 47 ms 328 KB # of queries: 2941
4 Correct 43 ms 328 KB # of queries: 2782
5 Correct 38 ms 360 KB # of queries: 2754
6 Correct 35 ms 352 KB # of queries: 2760
7 Correct 41 ms 328 KB # of queries: 2955
8 Correct 41 ms 468 KB # of queries: 2686
9 Correct 32 ms 340 KB # of queries: 2744
10 Correct 22 ms 328 KB # of queries: 1852
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: 5
15 Correct 3 ms 328 KB # of queries: 90
16 Correct 2 ms 328 KB # of queries: 165
17 Correct 319 ms 380 KB # of queries: 19778
18 Correct 326 ms 364 KB # of queries: 19317
19 Correct 431 ms 476 KB # of queries: 19730
20 Correct 212 ms 456 KB # of queries: 18260
21 Correct 335 ms 496 KB # of queries: 16821
22 Correct 347 ms 500 KB # of queries: 19988
23 Correct 359 ms 480 KB # of queries: 19878
24 Correct 149 ms 364 KB # of queries: 8929
25 Correct 351 ms 492 KB # of queries: 19198
26 Correct 300 ms 504 KB # of queries: 17829
27 Correct 140 ms 356 KB # of queries: 8893
28 Correct 379 ms 500 KB # of queries: 19821
29 Runtime error 343 ms 376 KB Execution killed with signal 13
30 Halted 0 ms 0 KB -