oj.uz

Submission #292278

# Submission time Handle Problem Language Result Execution time Memory
292278 2020-09-06T17:19:42 Z amiratou Hotter Colder (IOI10_hottercolder) C++14
78 / 100
 3697 ms 8312 KB 
#include "grader.h"
#include <bits/stdc++.h>
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
using namespace std;



map<pair<int,int>,int> mymap;


int HC(int N){
	mymap.clear();
	if(N==1)return 1;
	if(N==2){
		Guess(1);
		if(Guess(2)==1)return 2;
		return 1;
	}
	if(N==3){
		Guess(1);
		int k=Guess(3);
		if(!k)return 2;
		else if(k==1)return 3;
		else return 1;
	}
	int l=1,r=N,a,b,last=-1,h;
	if((r-l+1)<=5){
		Guess(l),h=Guess(r-2);
		if(!h)return l+1;
		else if(h==-1)return l;
		else{
			h=Guess(r);
			if(!h)return r-1;
			else if(h==1)return r;
			return r-2;
		}
	}
	while((r-l+1)>7){
		a=l+(r-l)/3,b=r-(r-l)/3;
		int med=(a+b)>>1;
		//cerr<<l<<" "<<r<<"\n";
		//cerr<<a<<" "<<b<<"\n";
		int A,B;
		if(mymap.count({a,b}))
			B=mymap[{a,b}];
		else{
			A=Guess(a),B=Guess(b),last=b;
			mymap[{a,b}]=B;
		}
		if(!B)return (a+b)/2;
		if(B==1)l=med+1;
		else r=med-(!((a+b)&1));
	}
	//cerr<<l<<" "<<r<<"\n";
	if((r-l+1)<=3){
		if(mymap.count({l,r}))
			h=mymap[{l,r}];
		else Guess(l),h=Guess(r);
		if(!h)return l+1;
		else if(h==1)return r;
		return l;
	}
	if((r-l+1)<=5){
		Guess(l),h=Guess(r-2);
		if(!h)return l+1;
		else if(h==-1)return l;
		else{
			h=Guess(r);
			if(!h)return r-1;
			else if(h==1)return r;
			return r-2;
		}
	}
	Guess(l),h=Guess(l+2);
	if(!h)return l+1;
	else if(h==-1)
		return l;
	else{
		h=Guess(r-2);
		if(!h)return r-3;
		else if(h==-1)return l+2;
		else{
			h=Guess(r);
			if(!h)return r-1;
			else if(h==1)return r;
			return r-2;
		}
	}
}

Compilation message

hottercolder.cpp: In function 'int HC(int)':
hottercolder.cpp:43:7: warning: variable 'A' set but not used [-Wunused-but-set-variable]
   43 |   int A,B;
      |       ^
hottercolder.cpp:26:18: warning: variable 'last' set but not used [-Wunused-but-set-variable]
   26 |  int l=1,r=N,a,b,last=-1,h;
      |                  ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1280 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 1280 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1280 KB Output is correct

Subtask #4
3.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 3697 ms 8312 KB Output is partially correct - alpha = 0.103448275862