oj.uz

Submission #50938

# Submission time Handle Problem Language Result Execution time Memory
50938 2018-06-15T06:47:09 Z spencercompton ICC (CEOI16_icc) C++17
0 / 100
 423 ms 852 KB 
#include "icc.h"
#include <bits/stdc++.h>

using namespace std;
 
int n;
void findRoad(){
	int a[n/2];
	int b[n-n/2];
	int ar[n];
	for(int i = 0; i<n; i++){
		ar[i] = i+1;
	}
	while(true){

		for(int i = 0; i+1<n; i++){
			int rem = n-i-1;
			int ra = i + (rand()%rem) + 1; 
			swap(ar[i],ar[ra]);
		}
		for(int i = 0; i<n; i++){
			if(i<n/2){
				a[i] = ar[i];
			}
			else{
				b[i-n/2] = ar[i];
			}
		}
		if(query(n/2,n-n/2,a,b)){
			int low1 = 0;
			int high1 = n/2-1;
			while(low1<high1){
				int mid = (low1+high1)/2;
				int ta[mid];
				for(int i = 0; i<mid; i++){
					ta[i] = a[i];
				}
				if(query(mid,n-n/2,ta,b)){
					high1 = mid;
				}
				else{
					low1 = mid+1;
				}
			}
			int low2 = 0;
			int high2 = n-n/2-1;
			while(low2<high2){
				int mid = (low2+high2)/2;
				int tb[mid];
				for(int i = 0; i<mid; i++){
					tb[i] = b[i];
				}
				if(query(n/2,mid,a,tb)){
					high1 = mid;
				}
				else{
					low1 = mid+1;
				}
			}
			int ans1 = a[low1];
			int ans2 = b[low2];
			if(ans1>ans2){
				swap(ans1,ans2);
			}
			setRoad(ans1,ans2);
			break;
		}
	}
}
 
void run(int N){
	n = N;
	for(int n=1; n<N; n++)
		findRoad();
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 194 ms 504 KB Number of queries more than 3000 out of 1500
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 352 ms 604 KB Number of queries more than 5000 out of 2500
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 423 ms 804 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 364 ms 804 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 313 ms 852 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 279 ms 852 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -