Submission #50938

#	Time	Username	Problem	Language	Result	Execution time	Memory
50938		spencercompton	ICC (CEOI16_icc)	C++17	0 / 100	423 ms	852 KiB

icc

#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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10