oj.uz

Submission #260369

# Submission time Handle Problem Language Result Execution time Memory
260369 2020-08-10T07:24:23 Z 임성재(#5050) Library (JOI18_library) C++17
0 / 100
 36 ms 632 KB 
#include "library.h"
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mp make_pair

static int p[1010];
static vector<int> M;
static vector<int> v[1010];
int n;

static void cl() {
	M.clear();
	M.resize(n, 0);
}

static int Find(int a) {
	return p[a] = p[a] == a ? a : Find(p[a]);
}

static void Union(int a, int b) {
	a = Find(a);
	b = Find(b);

	p[b] = a;

	cl();
	M[v[a].back() - 1] = M[v[b].front() - 1] = 1;

	if(Query(M) == 1) {
		for(auto i : v[b]) {
			v[a].eb(i);
		}
		v[b].clear();
		return;
	}

	reverse(all(v[b]));
	cl();
	M[v[a].back() - 1] = M[v[b].front() - 1] = 1;

	if(Query(M) == 1) {
		for(auto i : v[b]) {
			v[a].eb(i);
		}
		v[b].clear();
		return;
	}

	reverse(all(v[a]));
	cl();
	M[v[a].back() - 1] = M[v[b].front() - 1] = 1;

	if(Query(M) == 1) {
		for(auto i : v[b]) {
			v[a].eb(i);
		}
		v[b].clear();
		return;
	}

	reverse(all(v[b]));
	cl();
	M[v[a].back() - 1] = M[v[b].front() - 1] = 1;

	if(Query(M) == 1) {
		for(auto i : v[b]) {
			v[a].eb(i);
		}
		v[b].clear();
		return;
	}
}

void f(int s, int e, int x, int k) {
	//cout << s << " " << e << " " << x << " " << k << endl;
	if(s == e) {
		Union(s, x);

		/*cout << Find(x) << " : ";
		for(auto i : v[Find(x)]) 
			cout << i << " ";

		cout << endl;*/

		return;
	}

	int m = s + e >> 1;

	cl();

	M[x-1] = 1;

	int t = 1;

	for(int i=1; i<=m; i++) {
		if(Find(i) != i) continue;

		t++;

		for(auto j : v[i]) {
			//cout << i << " " << j << endl;
			M[j-1] = 1;
		}
	}

	//cout << "chk" << endl;
	//for(auto i : M) cout << i;
	//cout << endl;

	t -= Query(M);
	//cout << "!" << t << endl;

	if(t) f(s, m, x, t);
	if(k - t) f(m+1, e, x, k-t);
}

void Solve(int N)
{
	cl();
	n = N;
	for(int i=1; i<=N; i++) p[i] = i, v[i].eb(i);

	int sz = 0;
	for(int i=1; i<=N; i++) {
		cl();

		for(int j=1; j<=i; j++) M[j-1] = 1;

		int k = Query(M);

		//cout << i << "-" << k << endl;

		if(k < sz + 1) f(1, i-1, i, sz + 1 - k);
		//else cout << i << " ok" << endl;

		sz = k;
	}

	for(int i=1; i<=N; i++) {
		if(Find(i) == i) {
			Answer(v[i]);
		}
	}
}

Compilation message

library.cpp: In function 'void f(int, int, int, int)':
library.cpp:95:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s + e >> 1;
          ~~^~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -