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 14:59:30
Task:Contest
Sender:KnowYourArchitecture
Submission time:2017-05-27 14:59:30
Status:READY
Result:ACCEPTED

Show test data

Code

#include <bits/stdc++.h>

using namespace std;
int h[101010];
int a[101010];
int n,k;
int qa(int i){
    if(i<=0)return 1e9+7;
    if (i > n) return -1e9;
    if(a[i])return a[i];
    cout<<1<<' '<<i<<endl;
    cin>>a[i];
    return a[i];
}

int qh(int i){
    if(i<=0)return 1e9+7;
    if (i > n) return -1e9;
    if(h[i])return h[i];
    cout<<2<<' '<<i<<endl;
    cin>>h[i];
    return h[i];
}


int main() {
    cin>>n>>k;
    
    //for (int i = 1; i <= n; i++)
    //    cin >> h[i];
    //for (int i = 1; i <= n; i++)
    //    cin >> a[i];
    
    /*int sa = 1;
    int ea = k;
    while (sa < ea) {
        int ca = (sa+ea)/2;
        int ch = k-ca+1;
        if (qa(ca) < qh(ch)) sa = ca+1;
        else ea = ca;
    }*/
    int sa = 0;
    int ea = k;
    while (sa < ea) {
        int ca = (sa+ea+1)/2;
        int ch = k-ca;
        if (qa(ca) < qh(ch)) ea = ca-1;
        else sa = ca;
        //int ca = (sa+ea)/2;
        //int ch = k-ca;
        //if (qa(ca) > qh(ch)) ea = ca;
        //else sa = ca+1;
    }
    int boo = sa;
    sa = 0;
    ea = k;
    while (sa < ea) {
        int ca = (sa+ea+1)/2;
        int ch = k-ca;
        if (qa(ca) < qh(ch+1)) ea = ca-1;
        else sa = ca;
    }
    int foo = sa;
    //cout<<boo<<" "<<foo<<endl;
    
    if (boo >= foo)
        cout << "3 "<<qh(k-sa)<<endl;
    else
        cout << "3 "<<qa(sa)<<endl;
    /*for (int ca = k; ca >= 0; ca--) {
        int ch = k-ca;
        //cout<<ca<<":"<<qa(ca)<<" "<<ch<<":"<<qh(ch)<<endl;
        if (qa(ca) > qh(ch)) {
            cout << "Boo"<<qh(ch)<<endl;
            return 0;
        }
        //cout<<ca<<":"<<qa(ca)<<" "<<ch<<":"<<qh(ch+1)<<endl;
        if (qa(ca) > qh(ch+1)) {
            cout << "Foo"<<qa(ca)<<endl;
            return 0;
        }
    }*/
    
    //if (
    
    
    //cout << sa << " " << k-sa+1 << endl;
    
    /*int sa = 1;
    int ea = n;
    while (sa < ea) {
        int ca = (sa+ea)/2;
        int sh = 1;
        int eh = n;
        while (sh < eh) {
            int ch = (sh+eh+1)/2;
            if (qa(ca) < qh(ch)) sh = ch;
            else eh = ch-1;
        }
        if (ca+sh >= k) ea=ca;
        else sa=ca+1;
    }
    int ca = ea;
    int sh = 1;
    int eh = n;
    int ch = -1;
    while (sh < eh) {
        ch = (sh+eh+1)/2;
        if (qa(ca) < qh(ch)) sh = ch;
        else eh = ch-1;
    }
    cout << sa << " " << sh << endl;*/
    
    return 0;
    /*
    int sa=0,ea=n+1;
    int sh=0,eh=n+1;
    while(sa<ea){
        int ca=(sa+ea)/2;
        sh=0,eh=n+1;
        while(sh<eh){
            int ch=(sh+eh)/2;
            if(qa(ca)<qh(ch))sh=ch+1;
            else eh=ch;
        }
        std::cerr<<"db:"<<sh<<' '<<eh<<' '<<ca<<'\n';
        if(ca+sh > k)ea=ca;
        else sa=ca+1;
    }
    sh=0,eh=n+1;
    while(sh<eh){
        int ch=(sh+eh)/2;
        if(qa(sa)<qh(ch))sh=ch+1;
        else eh=ch;
    }
    cout<<sa<<' '<<sh<<'\n';
    return 0;*/
}