oj.uz

Submission #947080

# Submission time Handle Problem Language Result Execution time Memory
947080 2024-03-15T13:29:06 Z pcc Library (JOI18_library) C++17
100 / 100
 151 ms 980 KB 
#include <cstdio>
#include <vector>
#include "library.h"
#include <bits/stdc++.h>
using namespace std;

/*
vector<int> M(N);
int A = Query(M);
vector<int> res(N);
Answer(res);
*/

#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 1010;
vector<int> v;
vector<pii> edges;
vector<int> perm;
bitset<mxn> ch;
int N;

int ask(bitset<mxn> b){
	if(b.count() == 0)return 0;
	vector<int> re(N);
	for(int i = 0;i<N;i++){
		if(b[i])re[i] = 1;
		else re[i] = 0;
	}
	return Query(re);
}

bool check(int s,int now){
	ch.reset();
	int exp = v.size()-s+1;
	for(int i = s;i<v.size();i++){
		ch[v[i]] = true;
	}
	ch[now] = true;
	//cerr<<s<<":"<<now<<"::";
	//for(int i = 0;i<N;i++)//cerr<<(ch[i]?1:0);cerr<<":";
	int re = ask(ch);
	for(auto &i:edges){
		if(ch[i.fs]&&ch[i.sc])exp--;
	}
	//cerr<<re<<','<<exp<<endl;
	if(exp != re)return false;
	else return true;
}

int get_edge(int s,int now){
	int l = s,r = v.size()-1;
	while(l != r){
		int mid = (l+r+1)>>1;
		if(check(mid,now))r = mid-1;
		else l = mid;
	}
	return l;
}

void calc(int now){
	while(!check(0,now)){
		int s = get_edge(0,now);
		edges.push_back({v[s],now});
		//cerr<<v[s]<<":"<<now<<endl;
	}
	return;
}

vector<int> g[mxn];
vector<int> ans;

void dfs(int now){
	ch[now] = true;
	ans.push_back(now+1);
	for(auto nxt:g[now]){
		if(ch[nxt])continue;
		dfs(nxt);
	}
	return;
}

void Solve(int NN){
	//cerr<<"HI"<<endl;
	if(NN == 1){
		Answer(vector<int>(1,1));
		return;
	}
	N = NN;
	srand(time(NULL));
	for(int i = 0;i<N;i++)perm.push_back(i);
	//random_shuffle(perm.begin(),perm.end());
	for(auto &i:perm){
		if(!v.empty())calc(i);
		v.push_back(i);
	}
	for(auto &i:edges){
		g[i.fs].push_back(i.sc);
		g[i.sc].push_back(i.fs);
	}
	for(auto &i:edges){
		//cerr<<i.fs<<' '<<i.sc<<endl;
	}
	int st = 0;
	for(int i = 0;i<N;i++){
		if(g[i].size()==1)st = i;
	}
	ch.reset();
	dfs(st);
	//for(auto &i:ans)//cerr<<i<<' ';cerr<<endl;
	Answer(ans);
	return;
}

Compilation message

library.cpp: In function 'bool check(int, int)':
library.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i = s;i<v.size();i++){
      |                ~^~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:102:12: warning: unused variable 'i' [-Wunused-variable]
  102 |  for(auto &i:edges){
      |            ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 468 KB # of queries: 1713
2 Correct 14 ms 460 KB # of queries: 1706
3 Correct 16 ms 460 KB # of queries: 1786
4 Correct 13 ms 712 KB # of queries: 1783
5 Correct 15 ms 440 KB # of queries: 1796
6 Correct 17 ms 460 KB # of queries: 1791
7 Correct 17 ms 460 KB # of queries: 1784
8 Correct 14 ms 464 KB # of queries: 1686
9 Correct 12 ms 724 KB # of queries: 1788
10 Correct 7 ms 464 KB # of queries: 1077
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 2
13 Correct 0 ms 344 KB # of queries: 5
14 Correct 0 ms 344 KB # of queries: 10
15 Correct 1 ms 596 KB # of queries: 75
16 Correct 1 ms 456 KB # of queries: 158

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 468 KB # of queries: 1713
2 Correct 14 ms 460 KB # of queries: 1706
3 Correct 16 ms 460 KB # of queries: 1786
4 Correct 13 ms 712 KB # of queries: 1783
5 Correct 15 ms 440 KB # of queries: 1796
6 Correct 17 ms 460 KB # of queries: 1791
7 Correct 17 ms 460 KB # of queries: 1784
8 Correct 14 ms 464 KB # of queries: 1686
9 Correct 12 ms 724 KB # of queries: 1788
10 Correct 7 ms 464 KB # of queries: 1077
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 2
13 Correct 0 ms 344 KB # of queries: 5
14 Correct 0 ms 344 KB # of queries: 10
15 Correct 1 ms 596 KB # of queries: 75
16 Correct 1 ms 456 KB # of queries: 158
17 Correct 139 ms 464 KB # of queries: 11317
18 Correct 145 ms 724 KB # of queries: 11162
19 Correct 151 ms 464 KB # of queries: 11287
20 Correct 133 ms 472 KB # of queries: 10561
21 Correct 122 ms 476 KB # of queries: 9928
22 Correct 132 ms 472 KB # of queries: 11300
23 Correct 146 ms 468 KB # of queries: 11269
24 Correct 51 ms 720 KB # of queries: 5298
25 Correct 135 ms 472 KB # of queries: 11038
26 Correct 123 ms 712 KB # of queries: 10330
27 Correct 60 ms 464 KB # of queries: 5279
28 Correct 133 ms 468 KB # of queries: 10965
29 Correct 125 ms 724 KB # of queries: 10953
30 Correct 118 ms 980 KB # of queries: 10965