oj.uz

Submission #61696

# Submission time Handle Problem Language Result Execution time Memory
61696 2018-07-26T10:57:04 Z cki86201 Library (JOI18_library) C++11
100 / 100
 873 ms 696 KB 
#include "library.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;

int Get(vector <int> &X, int N) {
	vector <int> M(N);
	rep(i, N) M[i] = 0;
	for(int e : X) M[e] = 1;
	return Query(M);
}

void Solve(int N)
{
	if(N == 1) {
		vector <int> res; res.pb(1);
		Answer(res);
		return;
	}
	vector<int> M(N);
	
	for(int i = 0; i < N; i++) {
		M[i] = 1;
	}
	int st = -1;
	rep(i, N) {
		M[i] = 0;
		if(Query(M) == 1) { st = i; break; }
		M[i] = 1;
	}
	int chk[1010] = {};
	chk[st] = 1;
	vector<int> res(N);
	res[0] = st;
	for(int i=1;i<N;i++) {
		vector <int> v;
		rep(j, N) if(chk[j] == 0) {
			v.pb(j);
		}
		int m = szz(v);
		if(m == 1) { res[i] = v[0]; continue; }
		int lg = 32 - __builtin_clz(m-1);
		int idx = 0;
		rep(j, lg) {
			vector <int> w;
			rep(k, m) if(1<<j & k) w.pb(v[k]);
			int v1 = Get(w, N);
			w.pb(res[i-1]);
			int v2 = Get(w, N);
			if(v1 == v2) idx |= 1<<j;
		}
		res[i] = v[idx];
		chk[v[idx]] = 1;
	}

	for(int i = 0; i < N; i++) {
		res[i] += 1;
	}

	Answer(res);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 296 KB Output is correct
2 Correct 67 ms 312 KB Output is correct
3 Correct 44 ms 356 KB Output is correct
4 Correct 100 ms 408 KB Output is correct
5 Correct 81 ms 420 KB Output is correct
6 Correct 71 ms 420 KB Output is correct
7 Correct 77 ms 484 KB Output is correct
8 Correct 42 ms 484 KB Output is correct
9 Correct 94 ms 496 KB Output is correct
10 Correct 34 ms 496 KB Output is correct
11 Correct 3 ms 496 KB Output is correct
12 Correct 3 ms 496 KB Output is correct
13 Correct 3 ms 496 KB Output is correct
14 Correct 4 ms 496 KB Output is correct
15 Correct 3 ms 552 KB Output is correct
16 Correct 7 ms 552 KB Output is correct

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 296 KB Output is correct
2 Correct 67 ms 312 KB Output is correct
3 Correct 44 ms 356 KB Output is correct
4 Correct 100 ms 408 KB Output is correct
5 Correct 81 ms 420 KB Output is correct
6 Correct 71 ms 420 KB Output is correct
7 Correct 77 ms 484 KB Output is correct
8 Correct 42 ms 484 KB Output is correct
9 Correct 94 ms 496 KB Output is correct
10 Correct 34 ms 496 KB Output is correct
11 Correct 3 ms 496 KB Output is correct
12 Correct 3 ms 496 KB Output is correct
13 Correct 3 ms 496 KB Output is correct
14 Correct 4 ms 496 KB Output is correct
15 Correct 3 ms 552 KB Output is correct
16 Correct 7 ms 552 KB Output is correct
17 Correct 746 ms 560 KB Output is correct
18 Correct 766 ms 564 KB Output is correct
19 Correct 704 ms 564 KB Output is correct
20 Correct 609 ms 564 KB Output is correct
21 Correct 467 ms 564 KB Output is correct
22 Correct 710 ms 564 KB Output is correct
23 Correct 846 ms 564 KB Output is correct
24 Correct 238 ms 564 KB Output is correct
25 Correct 869 ms 692 KB Output is correct
26 Correct 676 ms 692 KB Output is correct
27 Correct 259 ms 696 KB Output is correct
28 Correct 830 ms 696 KB Output is correct
29 Correct 873 ms 696 KB Output is correct
30 Correct 673 ms 696 KB Output is correct