oj.uz

Submission #50944

# Submission time Handle Problem Language Result Execution time Memory
50944 2018-06-15T07:00:00 Z spencercompton ICC (CEOI16_icc) C++17
0 / 100
 7 ms 752 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
// int query(int a, int b, int c[], int d[]){
// 	cout << "A " << endl;
// 	for(int i = 0; i<a; i++){
// 		cout << c[i] << " ";
// 	}
// 	cout << endl;
// 	for(int i = 0; i<b; i++){
// 		cout << d[i] << " ";
// 	}
// 	cout << endl;
// 	int x;
// 	cin >> x;
// 	return x;
// }
// void setRoad(int a, int b){
// 	cout << "! " << a << "  " << b << endl;
// }
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+1];
				for(int i = 0; i<=mid; i++){
					ta[i] = a[i];
				}
				if(query(mid+1,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+1];
				for(int i = 0; i<=mid; i++){
					tb[i] = b[i];
				}
				if(query(n/2,mid+1,a,tb)){
					high2 = mid;
				}
				else{
					low2 = 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();
}
// int main(){
// 	run(4);
// }

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 504 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 612 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 688 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 692 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 752 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 752 KB Wrong road!
2 Halted 0 ms 0 KB -