oj.uz

답안 #722370

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
722370 2023-04-11T20:48:50 Z FatihSolak 도서관 (JOI18_library) C++17
19 / 100
 315 ms 476 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
void Solve(int N){
	if(N == 1){
		Answer({1});
		return;
	}
	vector<int> M(N);
	auto ask = [&](vector<int> &v){
		fill(M.begin(),M.end(),0);
		for(auto u:v){
			M[u] = 1;
		}
		return Query(M);
	};
	auto ok = [&](vector<int> v,int x)->bool{
		if(v.empty())
			return false;
		int tmp = ask(v);
		v.push_back(x);
		return ask(v) <= tmp;
	};
	vector<int> adj[N];
	vector<bool> used(N,0);
	queue<int> q;
	used[0] = 1;
	q.push(0);
	q.push(0);
	while(q.size()){
		int tp = q.front();
		q.pop();
		vector<int> v;
		for(int i = 0;i<N;i++){
			if(!used[i])
				v.push_back(i);
		}
		if(!ok(v,tp))continue;
		while(v.size() > 1){
			vector<int> a;
			while(a.size() < v.size()){
				if(v.empty()){
					Answer({});
					exit(0);
				}
				a.push_back(v.back());
				v.pop_back();
			}
			if(!ok(v,tp)){
				v = a;
			}
		}
		if(!ok(v,tp))continue;
		if(v.empty()){
			Answer({});
			exit(0);
		}
		q.push(v[0]);
		used[v[0]] = 1;
		adj[tp].push_back(v[0]);
		adj[v[0]].push_back(tp);
	}
	if(N > 200){
		Answer({});
		exit(0);
	}
	vector<int> res;
	for(int i = 0;i<N;i++){
		if(adj[i].size() == 1){
			int now = i;
			while(1){
				int tmp = -1;
				if(res.size())
					tmp = res.back();
				res.push_back(now);
				if(res.size() == N)
					break;
				for(auto u:adj[now]){
					if(u != tmp){
						now = u;
						break;
					}
				}	
			}
			break;
		}
	}
	for(auto &u:res)
		u++;
	Answer(res);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:76:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |     if(res.size() == N)
      |        ~~~~~~~~~~~^~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 324 KB # of queries: 3142
2 Correct 43 ms 316 KB # of queries: 3120
3 Correct 46 ms 316 KB # of queries: 3288
4 Correct 59 ms 312 KB # of queries: 3298
5 Correct 44 ms 312 KB # of queries: 3300
6 Correct 47 ms 208 KB # of queries: 3304
7 Correct 46 ms 316 KB # of queries: 3278
8 Correct 36 ms 308 KB # of queries: 3166
9 Correct 46 ms 304 KB # of queries: 3278
10 Correct 22 ms 208 KB # of queries: 1950
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 1 ms 208 KB # of queries: 4
13 Correct 1 ms 208 KB # of queries: 10
14 Correct 1 ms 208 KB # of queries: 20
15 Correct 2 ms 208 KB # of queries: 130
16 Correct 4 ms 208 KB # of queries: 282

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 324 KB # of queries: 3142
2 Correct 43 ms 316 KB # of queries: 3120
3 Correct 46 ms 316 KB # of queries: 3288
4 Correct 59 ms 312 KB # of queries: 3298
5 Correct 44 ms 312 KB # of queries: 3300
6 Correct 47 ms 208 KB # of queries: 3304
7 Correct 46 ms 316 KB # of queries: 3278
8 Correct 36 ms 308 KB # of queries: 3166
9 Correct 46 ms 304 KB # of queries: 3278
10 Correct 22 ms 208 KB # of queries: 1950
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 1 ms 208 KB # of queries: 4
13 Correct 1 ms 208 KB # of queries: 10
14 Correct 1 ms 208 KB # of queries: 20
15 Correct 2 ms 208 KB # of queries: 130
16 Correct 4 ms 208 KB # of queries: 282
17 Runtime error 315 ms 476 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -