oj.uz

Submission #296854

# Submission time Handle Problem Language Result Execution time Memory
296854 2020-09-11T01:46:51 Z eggag32 Library (JOI18_library) C++17
19 / 100
 2000 ms 4480 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl
#define debug2(x, y) debug(x), debug(y)
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
const int mxN = 1005;
 
template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }
 
mt19937 rng((ll)std::chrono::steady_clock::now().time_since_epoch().count());
 
int pos[mxN][mxN];
vi g[mxN];
 
void Solve(int n){
	if(n == 1){
		vi ans = {1};
		Answer(ans);
		return;
	}
	int sz = n / 31; //the size of our guess bucket
	int num = (n * (n - 1)) / 2;
	int rem = 20000;
	memset(pos, -1, sizeof(pos));
	while((num + 5000) > rem){
		vi vis(n, 0), cr;
		rep(k, sz){
			while(true){
				int ind = rng() % n;
				if(!vis[ind]){
					vis[ind] = 1;
					cr.pb(ind);
					break;
				}
			}
		}
		int ans = Query(vis);
		if(ans == sz){
			rep(i, cr.size()) rep(j, cr.size()) if(i != j && pos[cr[i]][cr[j]] == -1){
				num--;
				pos[cr[i]][cr[j]] = 0;
				pos[cr[j]][cr[i]] = 0;
			}		
		}
		rem--;
	}
	vi nw(n, 0);
	pi prev = {-1, -1};
	rep(i, n) rep(j, n) if(i != j && pos[i][j] == -1){
		if(prev.fi != -1) nw[prev.fi] = nw[prev.se] = 0;
		nw[i] = nw[j] = 1;
		prev = mp(i, j);
		int ans = Query(nw);
		if(ans == 1) pos[i][j] = pos[j][i] = 1;
		else pos[i][j] = pos[j][i] = 0;
	}
	//now we know all the comparisons so we can just reconstruct the answer
	int st = -1;
	rep(i, n){
		rep(j, n){
			if(pos[i][j] == 1) g[i].pb(j);
		}
		if(g[i].size() == 1) st = i;
	}
	vi ans;
	ans.pb(st + 1);
	int nxt = g[st][0];
	repn(i, 1, n){
		ans.pb(nxt + 1);
		rep(j, g[nxt].size()){
			if((ans[(int)ans.size() - 2] - 1) != g[nxt][j]){
				nxt = g[nxt][j];
				break;
			}
		}
	}
	Answer(ans);
	return;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 4472 KB # of queries: 14992
2 Correct 203 ms 4472 KB # of queries: 14995
3 Correct 248 ms 4352 KB # of queries: 14993
4 Correct 176 ms 4352 KB # of queries: 14993
5 Correct 205 ms 4352 KB # of queries: 14997
6 Correct 199 ms 4472 KB # of queries: 14993
7 Correct 204 ms 4344 KB # of queries: 14999
8 Correct 213 ms 4472 KB # of queries: 14990
9 Correct 206 ms 4352 KB # of queries: 14997
10 Correct 111 ms 4344 KB # of queries: 8256
11 Correct 0 ms 384 KB # of queries: 0
12 Correct 3 ms 4224 KB # of queries: 1
13 Correct 3 ms 4480 KB # of queries: 3
14 Correct 3 ms 4352 KB # of queries: 6
15 Correct 4 ms 4224 KB # of queries: 105
16 Correct 8 ms 4224 KB # of queries: 351

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 4472 KB # of queries: 14992
2 Correct 203 ms 4472 KB # of queries: 14995
3 Correct 248 ms 4352 KB # of queries: 14993
4 Correct 176 ms 4352 KB # of queries: 14993
5 Correct 205 ms 4352 KB # of queries: 14997
6 Correct 199 ms 4472 KB # of queries: 14993
7 Correct 204 ms 4344 KB # of queries: 14999
8 Correct 213 ms 4472 KB # of queries: 14990
9 Correct 206 ms 4352 KB # of queries: 14997
10 Correct 111 ms 4344 KB # of queries: 8256
11 Correct 0 ms 384 KB # of queries: 0
12 Correct 3 ms 4224 KB # of queries: 1
13 Correct 3 ms 4480 KB # of queries: 3
14 Correct 3 ms 4352 KB # of queries: 6
15 Correct 4 ms 4224 KB # of queries: 105
16 Correct 8 ms 4224 KB # of queries: 351
17 Execution timed out 3077 ms 4352 KB Time limit exceeded
18 Halted 0 ms 0 KB -