oj.uz

Submission #697182

# Submission time Handle Problem Language Result Execution time Memory
697182 2023-02-08T17:36:05 Z amunduzbaev Park (JOI17_park) C++17
10 / 100
 249 ms 904 KB 
#include "park.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

mt19937 rng(chrono :: steady_clock :: now().time_since_epoch().count());
#define rnd(l, r) uniform_int_distribution<int>(l, r)(rng)

static int used[1400];
void Detect(int t, int n){
	auto ask = [&](int a, int b){
		if(a > b) swap(a, b);
		int ans = Ask(a, b, used);
		return ans;
	};
	
	auto Ans = [&](int i, int j){
		if(i > j) swap(i, j);
		Answer(i, j);
	};
	
	function<void(int, int, vector<int>)> dfs = [&](int l, int r, vector<int> tot){
		//~ cout<<l<<" ";
		//~ for(auto x : tot) cout<<x<<" ";
		//~ cout<<r<<" ";
		//~ cout<<"\n";
		if(tot.empty()){
			Ans(l, r);
			return;
		}
		shuffle(tot.begin(), tot.end(), rng);
		int v = tot[rnd(0, (int)tot.size() - 1)];
		vector<int> L, R;
		used[l] = used[r] = 1;
		for(auto x : tot) used[x] = 1;
		for(auto x : tot){
			if(x == v) continue;
			used[x] = 0;
			if(ask(l, v)){
				R.push_back(x);
			} else {
				used[x] = 1;
				L.push_back(x);
			}
		}
		
		for(auto x : L) used[x] = 0;
		used[l] = used[r] = used[v] = 0;
		dfs(l, v, L);
		dfs(v, r, R);
	};
	
	vector<int> tot(n - 2);
	iota(tot.begin(), tot.end(), 1);
	dfs(0, n - 1, tot);
}


/*

1
7
6
0 4
4 3
3 1
1 2
2 5
5 6

1
6
7
0 1
0 3
1 2
1 4
2 4
2 5
3 4

*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Wrong Answer[2]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 648 KB Output is correct
2 Correct 22 ms 524 KB Output is correct
3 Correct 25 ms 468 KB Output is correct
4 Correct 40 ms 536 KB Output is correct
5 Correct 31 ms 516 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 848 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 720 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 249 ms 904 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -