oj.uz

답안 #954558

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954558 2024-03-28T07:00:57 Z Sharky 도서관 (JOI18_library) C++17
19 / 100
 209 ms 720 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

void clr(vector<int>& vt) {
	for (int i = 0; i < vt.size(); i++) vt[i] = 0;
}

random_device rd;
mt19937 g(rd());
int outn;

int query(vector<int>& v) {
	vector<int> vt(outn, 0);
	for (auto x : v) vt[x - 1] = 1;
	v.clear();
	return Query(vt);
}

vector<int> adj[1001], ans;

void dfs(int u, int p = -1) {
	ans.push_back(u);
	for (int v : adj[u]) if (v != p) dfs(v, u);
}

void Solve(int n) {
	if (n == 1) {
		ans = {1};
		Answer(ans);
		return;
	}
	outn = n;
	vector<int> ee;
	vector<int> deg(n+1, 2), cand, vt;
	for (int sk = 1; sk <= n; sk++) {
		for (int i = 1; i <= n; i++) if (i != sk) vt.push_back(i);
		if (query(vt) == 1) ee.push_back(sk), deg[sk]--;
		cand.push_back(sk);
	}
	int ender = ee[0], i = ee[0], o = ee[1];
	while (i != o) {
		int sz = cand.size();
		int rt = sqrt(sz), nxt;
		shuffle(cand.begin(), cand.end(), g);
		vector<int> er;
		for (int j = 0; j < sz; j += rt) {
			for (int k = j; k < min(sz, j + rt); k++) {
				vt.push_back(cand[k]);
				if (cand[k] == i) continue;
			}
			vector<int> vt2 = vt;
			vt2.push_back(i);
			int extra = query(vt2) - query(vt);
			if (extra) continue;
			for (int k = j; k < min(sz, j + rt); k++) {
				if (cand[k] == i) continue;
				vt.push_back(i);
				vt.push_back(cand[k]);
				if (query(vt) == 1) {
					deg[cand[k]]--, deg[i]--;
					adj[cand[k]].push_back(i);
					adj[i].push_back(cand[k]);
					nxt = cand[k];
					if (!deg[cand[k]]) er.push_back(k);
					break;
				}
			}
			if (!deg[i]) break;
		}
		reverse(er.begin(), er.end());
		for (auto x : er) cand.erase(cand.begin() + x);
		for (int j = cand.size() - 1; j >= 0; j--) if (cand[j] == i) {
			cand.erase(cand.begin() + j);
			break;
		}
		i = nxt;
	}
	dfs(ender);
	Answer(ans);
}

Compilation message

library.cpp: In function 'void clr(std::vector<int>&)':
library.cpp:6:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |  for (int i = 0; i < vt.size(); i++) vt[i] = 0;
      |                  ~~^~~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:77:5: warning: 'nxt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |   i = nxt;
      |   ~~^~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 476 KB # of queries: 4007
2 Correct 35 ms 708 KB # of queries: 3768
3 Correct 25 ms 476 KB # of queries: 4099
4 Correct 35 ms 712 KB # of queries: 4228
5 Correct 40 ms 708 KB # of queries: 4039
6 Correct 37 ms 720 KB # of queries: 3963
7 Correct 35 ms 480 KB # of queries: 4070
8 Correct 37 ms 476 KB # of queries: 3929
9 Correct 31 ms 464 KB # of queries: 4139
10 Correct 16 ms 476 KB # of queries: 2163
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 5
13 Correct 0 ms 344 KB # of queries: 15
14 Correct 0 ms 344 KB # of queries: 18
15 Correct 1 ms 344 KB # of queries: 100
16 Correct 2 ms 344 KB # of queries: 256

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 476 KB # of queries: 4007
2 Correct 35 ms 708 KB # of queries: 3768
3 Correct 25 ms 476 KB # of queries: 4099
4 Correct 35 ms 712 KB # of queries: 4228
5 Correct 40 ms 708 KB # of queries: 4039
6 Correct 37 ms 720 KB # of queries: 3963
7 Correct 35 ms 480 KB # of queries: 4070
8 Correct 37 ms 476 KB # of queries: 3929
9 Correct 31 ms 464 KB # of queries: 4139
10 Correct 16 ms 476 KB # of queries: 2163
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 5
13 Correct 0 ms 344 KB # of queries: 15
14 Correct 0 ms 344 KB # of queries: 18
15 Correct 1 ms 344 KB # of queries: 100
16 Correct 2 ms 344 KB # of queries: 256
17 Runtime error 209 ms 488 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -