Submission #253835

#	Time	Username	Problem	Language	Result	Execution time	Memory
253835		TadijaSebez	Hotter Colder (IOI10_hottercolder)	C++11	100 / 100	1075 ms	22880 KiB

hottercolder

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
const int L=30;
int n,magic[L];
int Search(int l,int r,int last){
	if(l==r)return l;
	if(l>r)swap(l,r);
	int sz=3;
	while(sz<r-l+1)sz=sz*2+1;
	int mid;
	if(r-sz+1>last)mid=r-sz/2;
	else if(l+sz-1<last)mid=l+sz/2;
	else if(last<=l)mid=last+sz/2;
	else mid=last-sz/2;
	int nxt=mid*2-last;
	int g=Guess(nxt);
	if(g==0)return mid;
	if((g>0)^(last<nxt))return Search(l,max(l,mid-1),nxt);
	else return Search(min(r,mid+1),r,nxt);
}
int get(int x,bool inv){return inv?n-x+1:x;}
int Solve(int sz,bool inv){
	if(sz==1)return get(1,inv);
	if(sz==2)return Guess(get(1,inv))>0?get(1,inv):get(2,inv);
	if(sz==3){
		int g=Guess(get(1,inv));
		return g==0?get(2,inv):g>0?get(1,inv):get(3,inv);
	}
	if(sz==4){
		int g=Guess(get(3,inv));
		if(g<0)return get(4,inv);
		g=Guess(get(1,inv));
		return g>0?get(1,inv):g==0?get(2,inv):get(3,inv);
	}
	if(sz==5){
		int g=Guess(get(3,inv));
		if(g<0)return get(5,inv);
		if(g==0)return get(4,inv);
		g=Guess(get(1,inv));
		return g>0?get(1,inv):g==0?get(2,inv):get(3,inv);
	}
	if(sz==6){
		int g=Guess(get(1,inv));
		if(g>0){
			g=Guess(get(3,inv));
			return g>0?get(3,inv):g==0?get(2,inv):get(1,inv);
		}else{
			g=Guess(get(9,inv));
			return g>0?get(6,inv):g==0?get(5,inv):get(4,inv);
		}
	}
	if(sz==7){
		int g=Guess(get(1,inv));
		if(g>0){
			g=Guess(get(3,inv));
			return g>0?get(3,inv):g==0?get(2,inv):get(1,inv);
		}else if(g<0){
			g=Guess(get(11,inv));
			return g>0?get(7,inv):g==0?get(6,inv):get(5,inv);
		}else return get(4,inv);
	}
	int ptr=0;
	while(magic[ptr]<sz)ptr++;
	int tmp=magic[ptr-2];
	int g=Guess(get(tmp-2,inv));
	if(g==0)return get((tmp-2+sz)/2,inv);
	if(g<0)return Search(get((tmp-2+sz)/2+1,inv),get(sz,inv),get(tmp-2,inv));
	g=Guess(get(tmp,inv));
	return g==0?get(tmp-1,inv):g<0?Solve(tmp,inv):Search(get(tmp,inv),get((tmp-2+sz-1)/2,inv),get(tmp,inv));
}
int HC(int N){
	n=N;
	if(n==1)return 1;
	if(n==2){
		Guess(1);
		return Guess(2)>0?2:1;
	}
	if(n==3){
		Guess(1);
		int g=Guess(3);
		return g<0?1:g==0?2:3;
	}
	magic[0]=1;
	magic[1]=3;
	magic[2]=7;
	for(int i=3;i<L;i++)magic[i]=magic[i-2]+(1<<i);
	int mid=n/2+1;
	Guess(mid-2);
	int g=Guess(mid);
	return g==0?mid-1:g<0?Solve(mid,0):Solve(n-mid+1,1);
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25