oj.uz

Submission #504039

# Submission time Handle Problem Language Result Execution time Memory
504039 2022-01-09T14:50:23 Z AriaH Library (JOI18_library) C++17
100 / 100
 194 ms 23904 KB 
/** I can do this all day **/

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "library.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file_io freopen("inupt.txt", "r+", stdin); freopen("output.txt", "w+", stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const int LOG = 20;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

int n;

vector < int > Q, G[N];

vector < pii > E;
/*
int Query(vector < int > vec)
{
	printf("query : \n");
	for(int i = 0; i < n; i ++)
	{
		printf("%d ", vec[i]);
	}
	int x;
	scanf("%d", &x);
	return x;
}

void Answer(vector < int > vec)
{
	printf("ans : \n");
	for(auto x : vec) printf("%d ", x);
	printf("\n");
}
*/

void add(int a, int b)
{
	///printf("fine %d %d\n", a, b);
	a ++, b ++;
	G[a].push_back(b);
	G[b].push_back(a);
	E.push_back({a - 1, b - 1});
}

void Fill(int l, int r)
{
	for(int i = 0; i < l; i ++) Q[i] = 0;
	for(int i = r + 1; i < n; i ++) Q[i] = 0;
	for(int i = l; i <= r; i ++) Q[i] = 1;
}

inline int ask(int l, int r, int i)
{
	if(l > r) return 0;
	Fill(l, r);
	Q[i] = 1;
	int T = r - l + 2;
	int cu = T - Query(Q);
	for(auto [a, b] : E)
	{
		if(Q[a] && Q[b]) cu --;
	}
	return cu;
}

void Solve(int _n)
{
	n = _n;
	Q.clear();
	Q.resize(n, 0);
	E.clear();
	for(int i = 0; i < n; i ++) G[i].clear();
	for(int i = 1; i < n; i ++)
	{
		int e = ask(0, i - 1, i);
		while(e --)
		{
			int d = 0, up = i;
			while(up - d > 1)
			{
				int mid = (up + d) >> 1;
				if(ask(mid, i - 1, i))
				{
					d = mid;
				}
				else
				{
					up = mid;
				}
			}
			add(i, d);
		}
	}
	int st = -1, last = 0;
	for(int i = 1; i <= n; i ++) if(SZ(G[i]) == 1 || (st == -1 && i == n)) st = i;
	vector < int > Ans;
	assert(st != -1);
	while(1)
	{
		int nxt = 0;
		Ans.push_back(st);
		for(auto now : G[st]) nxt ^= now;
		nxt ^= last;
		last = st;
		st = nxt;
		if(st == 0) break;
	}
	Answer(Ans);
}
/*
int main()
{
	scanf("%d", &n);
	Solve(n);

	return 0;
}*/

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23780 KB # of queries: 1522
2 Correct 33 ms 23824 KB # of queries: 1516
3 Correct 35 ms 23784 KB # of queries: 1587
4 Correct 36 ms 23768 KB # of queries: 1584
5 Correct 33 ms 23780 KB # of queries: 1597
6 Correct 37 ms 23752 KB # of queries: 1592
7 Correct 38 ms 23784 KB # of queries: 1585
8 Correct 32 ms 23784 KB # of queries: 1494
9 Correct 40 ms 23788 KB # of queries: 1590
10 Correct 32 ms 23768 KB # of queries: 949
11 Correct 14 ms 23776 KB # of queries: 0
12 Correct 14 ms 23748 KB # of queries: 1
13 Correct 14 ms 23740 KB # of queries: 3
14 Correct 14 ms 23684 KB # of queries: 7
15 Correct 16 ms 23752 KB # of queries: 61
16 Correct 16 ms 23752 KB # of queries: 132

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23780 KB # of queries: 1522
2 Correct 33 ms 23824 KB # of queries: 1516
3 Correct 35 ms 23784 KB # of queries: 1587
4 Correct 36 ms 23768 KB # of queries: 1584
5 Correct 33 ms 23780 KB # of queries: 1597
6 Correct 37 ms 23752 KB # of queries: 1592
7 Correct 38 ms 23784 KB # of queries: 1585
8 Correct 32 ms 23784 KB # of queries: 1494
9 Correct 40 ms 23788 KB # of queries: 1590
10 Correct 32 ms 23768 KB # of queries: 949
11 Correct 14 ms 23776 KB # of queries: 0
12 Correct 14 ms 23748 KB # of queries: 1
13 Correct 14 ms 23740 KB # of queries: 3
14 Correct 14 ms 23684 KB # of queries: 7
15 Correct 16 ms 23752 KB # of queries: 61
16 Correct 16 ms 23752 KB # of queries: 132
17 Correct 168 ms 23788 KB # of queries: 10318
18 Correct 132 ms 23780 KB # of queries: 10174
19 Correct 174 ms 23784 KB # of queries: 10288
20 Correct 194 ms 23820 KB # of queries: 9620
21 Correct 170 ms 23800 KB # of queries: 9036
22 Correct 191 ms 23788 KB # of queries: 10301
23 Correct 188 ms 23904 KB # of queries: 10271
24 Correct 88 ms 23772 KB # of queries: 4786
25 Correct 170 ms 23784 KB # of queries: 10060
26 Correct 177 ms 23768 KB # of queries: 9408
27 Correct 82 ms 23760 KB # of queries: 4769
28 Correct 129 ms 23800 KB # of queries: 9966
29 Correct 148 ms 23804 KB # of queries: 9955
30 Correct 160 ms 23804 KB # of queries: 9966