oj.uz

답안 #475387

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
475387 2021-09-22T09:05:11 Z prvocislo 도서관 (JOI18_library) C++17
0 / 100
 54 ms 320 KB 
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

const int maxn = 1005;
vector<int> g[maxn], ans;
bool vis[maxn];
int n;
vector<pair<int, int> > e;
int count_edges(int l, int r)
{
	int cnt = 0;
	for (pair<int, int> i : e) cnt += (l <= i.first && i.second <= r);
	return cnt;
}
bool extra_edge(int l, int r)
{
	vector<int> ask(n, 0);
	for (int i = l; i <= r; i++)
		ask[i] = 1;
	int e = r - l + 1 - Query(ask);
	return e > count_edges(l, r);
}
void dfs(int u)
{
	ans.push_back(u+1);
	vis[u] = true;
	for (int v : g[u]) if (!vis[v])
		dfs(v);
}
void Solve(int N)
{
	n = N;
	for (int it = 0; it < n - 1; it++)
	{
		int li = 1, ri = n - 1;
		while (li < ri)
		{
			int mi = (li + ri) >> 1;
			if (extra_edge(0, mi)) ri = mi;
			else li = mi + 1;
		}
		int lj = 0, rj = ri - 1;
		while (lj < rj)
		{
			int mj = (lj + rj + 1) >> 1;
			if (extra_edge(mj, ri)) lj = mj;
			else rj = mj - 1;
		}
		e.push_back({ rj, ri });
		g[ri].push_back(rj);
		g[rj].push_back(ri);
	}
	for (int i = 0; i < n; i++) if (g[i].size() == 1)
	{
		dfs(i);
		break;
	}
	Answer(ans);
}

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 200 KB # of queries: 2792
2 Correct 42 ms 200 KB # of queries: 2777
3 Correct 32 ms 320 KB # of queries: 2922
4 Correct 53 ms 200 KB # of queries: 2915
5 Correct 37 ms 304 KB # of queries: 2928
6 Correct 54 ms 320 KB # of queries: 2930
7 Correct 50 ms 316 KB # of queries: 2920
8 Correct 48 ms 304 KB # of queries: 2777
9 Correct 52 ms 316 KB # of queries: 2911
10 Correct 31 ms 316 KB # of queries: 1717
11 Incorrect 0 ms 200 KB Wrong Answer [4]
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 200 KB # of queries: 2792
2 Correct 42 ms 200 KB # of queries: 2777
3 Correct 32 ms 320 KB # of queries: 2922
4 Correct 53 ms 200 KB # of queries: 2915
5 Correct 37 ms 304 KB # of queries: 2928
6 Correct 54 ms 320 KB # of queries: 2930
7 Correct 50 ms 316 KB # of queries: 2920
8 Correct 48 ms 304 KB # of queries: 2777
9 Correct 52 ms 316 KB # of queries: 2911
10 Correct 31 ms 316 KB # of queries: 1717
11 Incorrect 0 ms 200 KB Wrong Answer [4]
12 Halted 0 ms 0 KB -