oj.uz

Submission #947079

# Submission time Handle Problem Language Result Execution time Memory
947079 2024-03-15T13:28:08 Z pcc Library (JOI18_library) C++17
19 / 100
 2000 ms 3832 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:42:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   42 |  for(int i = 0;i<N;i++)cerr<<(ch[i]?1:0);cerr<<":";
      |  ^~~
library.cpp:42:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   42 |  for(int i = 0;i<N;i++)cerr<<(ch[i]?1:0);cerr<<":";
      |                                          ^~~~
library.cpp: In function 'void Solve(int)':
library.cpp:111:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  111 |  for(auto &i:ans)cerr<<i<<' ';cerr<<endl;
      |  ^~~
library.cpp:111:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  111 |  for(auto &i:ans)cerr<<i<<' ';cerr<<endl;
      |                               ^~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 1328 KB # of queries: 1713
2 Correct 415 ms 1496 KB # of queries: 1706
3 Correct 420 ms 1784 KB # of queries: 1786
4 Correct 439 ms 1716 KB # of queries: 1783
5 Correct 438 ms 1964 KB # of queries: 1796
6 Correct 442 ms 1512 KB # of queries: 1791
7 Correct 430 ms 1908 KB # of queries: 1784
8 Correct 391 ms 1548 KB # of queries: 1686
9 Correct 422 ms 1868 KB # of queries: 1788
10 Correct 171 ms 1492 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 1 ms 344 KB # of queries: 10
15 Correct 3 ms 600 KB # of queries: 75
16 Correct 8 ms 716 KB # of queries: 158

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 1328 KB # of queries: 1713
2 Correct 415 ms 1496 KB # of queries: 1706
3 Correct 420 ms 1784 KB # of queries: 1786
4 Correct 439 ms 1716 KB # of queries: 1783
5 Correct 438 ms 1964 KB # of queries: 1796
6 Correct 442 ms 1512 KB # of queries: 1791
7 Correct 430 ms 1908 KB # of queries: 1784
8 Correct 391 ms 1548 KB # of queries: 1686
9 Correct 422 ms 1868 KB # of queries: 1788
10 Correct 171 ms 1492 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 1 ms 344 KB # of queries: 10
15 Correct 3 ms 600 KB # of queries: 75
16 Correct 8 ms 716 KB # of queries: 158
17 Execution timed out 3026 ms 3832 KB Time limit exceeded
18 Halted 0 ms 0 KB -