Code Submission Evaluation System Login

CSES - HIIT Open 2017

HIIT Open 2017

Contest start:2017-05-27 11:00:00
Contest end:2017-05-27 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard


History
2017-05-27 11:45:49
Task:Contest
Sender:Game of Nolife
Submission time:2017-05-27 11:45:49
Status:READY
Result:ACCEPTED

Show test data

Code

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

int get1(int i){
	cout<<"1 "<<i<<endl;
	int x;
	cin>>x;
	return x;
}

int get2(int i){
	cout<<"2 "<<i<<endl;
	int x;
	cin>>x;
	return x;
}

void ans(int i){
	cout<<"3 "<<i<<endl;
	exit(0);
}

vector<pair<int, int> > s1;
vector<pair<int, int> > s2;

int n,k;

void lol1(int x){
	if (x<1||x>n) return;
	int a=get1(x);
	s1.push_back({a, x});
}

void lol2(int x){
	if (x<1||x>n) return;
	int a=get2(x);
	s2.push_back({a, x});
}

void go(int x){
	int mi=1;
	int ma=n;
	while (mi<=ma){
		int mid=(mi+ma)/2;
		int k1=mid;
		int k2=k-mid+x;
		if (k1<1) mi=mid+1;
		else if(k1>n) ma=mid-1;
		else if(k2<1) ma=mid-1;
		else if(k2>n) mi=mid+1;
		else{
			int a=get1(k1);
			int b=get2(k2);
			s1.push_back({a, k1});
			s2.push_back({b, k2});
			if (a>b){
				mi=mid+1;
			}
			else if(a<b){
				ma=mid-1;
			}
			else{
				assert(0);
			}
		}
	}
	lol1(mi-1+x);
	lol1(mi+x);
	lol1(mi+1+x);
	
	lol2(k-mi-1-x);
	lol2(k-mi-x);
	lol2(k-mi-x+1);
}

int main(){
	cin>>n>>k;
	go(0);
	go(1);
	sort(s1.rbegin(), s1.rend());
	sort(s2.rbegin(), s2.rend());
	int h1=0;
	int h2=0;
	int i2=0;
	for (int i=0;i<(int)s1.size();i++){
		while (i2<(int)s2.size()&&s2[i2].F>s1[i].F){
			h2=max(h2, s2[i2].S);
			if (h1+h2==k){
				ans(s2[i2].F);
			}
			i2++;
		}
		h1=max(h1, s1[i].S);
		if (h1+h2==k){
			ans(s1[i].F);
		}
	}
	while (i2<(int)s2.size()){
		h2=max(h2, s2[i2].S);
		if (h1+h2==k){
			ans(s2[i2].F);
		}
		i2++;
	}
}