oj.uz

Submission #101029

# Submission time Handle Problem Language Result Execution time Memory
101029 2019-03-16T04:41:39 Z Pro_ktmr Park (JOI17_park) C++14
10 / 100
 169 ms 4396 KB 
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair
#define PB push_back

#include"park.h"

int n;
bool memo[1400][1400];
bool already[1400][1400] = {};
bool great(int a, int b){ //a < b
	if(already[a][b]) return memo[a][b];
	already[a][b] = true;
	int P[1400];
	for(int i=0; i<n; i++) P[i] = 1;
	P[a] = 0;
	if(Ask(0, b, P) == 0) return memo[a][b] = true;
	else return memo[a][b] = false;
}

void Detect(int T, int N){
	if(T != 2) return;
	random_device rd;
	mt19937 g(rd());
    
	n = N;
	int p[1400];
	p[0] = 0;
	p[N-1] = N-1;
	queue<pair<int,vector<int>>> que;
	vector<int> v;
	for(int i=1; i<N-1; i++) v.PB(i);
	que.push(MP(1, v));
	while(!que.empty()){
		int left = que.front().first;
		v = que.front().second;
		que.pop();
		shuffle(v.begin(), v.end(), g);
		vector<int> vSmall,vLarge;
		for(int i=1; i<v.size(); i++){
			if(great(v[0], v[i])) vLarge.PB(v[i]);
			else vSmall.PB(v[i]);
		}
		p[left+vSmall.size()] = v[0];
		if(vSmall.size() > 0) que.push(MP(left, vSmall));
		if(vLarge.size() > 0) que.push(MP(left+vSmall.size()+1, vLarge));
	}
	//for(int i=0; i<N; i++) cout << p[i] << endl;
	for(int i=0; i<N-1; i++) Answer(min(p[i], p[i+1]), max(p[i], p[i+1]));
}

Compilation message

park.cpp: In function 'void Detect(int, int)':
park.cpp:41:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1; i<v.size(); i++){
                ~^~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 4208 KB Output is correct
2 Correct 124 ms 4396 KB Output is correct
3 Correct 115 ms 4344 KB Output is correct
4 Correct 165 ms 4356 KB Output is correct
5 Correct 169 ms 4216 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 23.0

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