oj.uz

답안 #221567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
221567 2020-04-10T13:46:18 Z dorijanlendvaj 도서관 (JOI18_library) C++14
100 / 100
 448 ms 3200 KB 
#include "library.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define vi vector<int>
#define vl vector<ll>
#define all(a) begin(a),end(a)

using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;

int n,col[1010],par[1010];
vi sa[1010];
vi ch[1010];
map<pii,int> ma;
vi sol;

void merge(int a,int b)
{
	ch[a].pb(b);
	ch[b].pb(a);
	bool cha=col[a]==col[b];
	a=par[a];
	b=par[b];
	for (auto x: sa[b])
	{
		sa[a].pb(x);
		par[x]=a;
		if (cha) col[x]^=1;
	}
}

void dfs(int i,int p=-1)
{
	sol.pb(i+1);
	for (auto a: ch[i]) if (a!=p) dfs(a,i);
}

int f(int l,int r)
{
	if (r<=l) return r-l+1;
	if (ma.find({l,r})!=ma.end()) return ma[{l,r}];
	vi v;
	for (int j=0;j<l;++j) v.pb(0);
	for (int j=l;j<=r;++j) v.pb(1);
	for (int j=r+1;j<n;++j) v.pb(0);
	return ma[{l,r}]=Query(v);
}

void Solve(int N)
{
	n=N;
	for (int i=0;i<n;++i) par[i]=i,col[i]=0,sa[i]={i};
	int la=0;
	while (la<n-1)
	{
		int c=f(0,la)-la;
		while (f(0,la)-la==c) ++la;
		int dif=c-(f(0,la)-la);
		int lo=-1,hi=la-1;
		while (lo<hi)
		{
			int mid=(lo+hi+1)/2;
			vi v(n);
			int cn=0;
			for (int i=mid;i<la;++i) if (col[i]==0) v[i]=1,++cn;
			v[la]=1,++cn;
			if (Query(v)==cn)
			{
				cn=0;
				v=vi(n,0);
				for (int i=mid;i<la;++i) if (col[i]==1) v[i]=1,++cn;
				v[la]=1,++cn;
				if (Query(v)==cn) hi=mid-1;
				else lo=mid;
			}
			else lo=mid;
		}
		merge(la,lo);
		if (dif==2)
		{
			int pre=lo;
			lo=-1,hi=la-1;
			while (lo<hi)
			{
				int mid=(lo+hi+1)/2;
				vi v(n);
				int cn=0;
				for (int i=mid;i<la;++i) if (col[i]==0 && i!=pre) v[i]=1,++cn;
				v[la]=1,++cn;
				if (Query(v)==cn)
				{
					cn=0;
					v=vi(n,0);
					for (int i=mid;i<la;++i) if (col[i]==1 && i!=pre) v[i]=1,++cn;
					v[la]=1,++cn;
					if (Query(v)==cn) hi=mid-1;
					else lo=mid;
				}
				else lo=mid;
			}
			merge(la,lo);
		}
	}
	for (int i=0;i<n;++i) if (ch[i].size()<=1)
	{
		dfs(i);
		break;
	}
	Answer(sol);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 384 KB # of queries: 2377
2 Correct 41 ms 384 KB # of queries: 2370
3 Correct 43 ms 384 KB # of queries: 2460
4 Correct 42 ms 444 KB # of queries: 2437
5 Correct 46 ms 384 KB # of queries: 2481
6 Correct 48 ms 384 KB # of queries: 2480
7 Correct 43 ms 384 KB # of queries: 2427
8 Correct 44 ms 512 KB # of queries: 2316
9 Correct 44 ms 384 KB # of queries: 2468
10 Correct 27 ms 384 KB # of queries: 1433
11 Correct 4 ms 384 KB # of queries: 0
12 Correct 5 ms 384 KB # of queries: 2
13 Correct 5 ms 384 KB # of queries: 7
14 Correct 5 ms 416 KB # of queries: 12
15 Correct 5 ms 428 KB # of queries: 86
16 Correct 7 ms 384 KB # of queries: 204

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 384 KB # of queries: 2377
2 Correct 41 ms 384 KB # of queries: 2370
3 Correct 43 ms 384 KB # of queries: 2460
4 Correct 42 ms 444 KB # of queries: 2437
5 Correct 46 ms 384 KB # of queries: 2481
6 Correct 48 ms 384 KB # of queries: 2480
7 Correct 43 ms 384 KB # of queries: 2427
8 Correct 44 ms 512 KB # of queries: 2316
9 Correct 44 ms 384 KB # of queries: 2468
10 Correct 27 ms 384 KB # of queries: 1433
11 Correct 4 ms 384 KB # of queries: 0
12 Correct 5 ms 384 KB # of queries: 2
13 Correct 5 ms 384 KB # of queries: 7
14 Correct 5 ms 416 KB # of queries: 12
15 Correct 5 ms 428 KB # of queries: 86
16 Correct 7 ms 384 KB # of queries: 204
17 Correct 448 ms 760 KB # of queries: 16180
18 Correct 436 ms 888 KB # of queries: 15999
19 Correct 441 ms 760 KB # of queries: 16173
20 Correct 397 ms 640 KB # of queries: 15115
21 Correct 375 ms 612 KB # of queries: 14160
22 Correct 439 ms 672 KB # of queries: 16070
23 Correct 442 ms 604 KB # of queries: 16080
24 Correct 153 ms 524 KB # of queries: 7445
25 Correct 435 ms 652 KB # of queries: 15726
26 Correct 395 ms 632 KB # of queries: 14774
27 Correct 165 ms 632 KB # of queries: 7488
28 Correct 279 ms 3192 KB # of queries: 9976
29 Correct 279 ms 3200 KB # of queries: 9965
30 Correct 282 ms 3192 KB # of queries: 9976