Submission #1260010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260010		Szymon_Pilipczuk	Worm Worries (BOI18_worm)	C++20	10 / 100	8 ms	416 KiB

worm

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e18;
    int n,m,k,q;

int c = 0;
void debug()
{
    c++;
    if(c > q)
    {
        exit(0);
    }
}
int main()
{
    cin>>n>>m>>k>>q;
    pair<pair<int,int>,pair<int,int>> bb;
    bb = {{1,n},{1,m}};
    pair<int,pair<int,int>> tmx = {-1,{-1,-1}};
    while(bb.st.st != bb.st.nd || bb.nd.st != bb.nd.nd)
    {
        if(bb.st.nd - bb.st.st > bb.nd.nd - bb.nd.st)
        {
            int mid = (bb.st.st+bb.st.nd)/2;
            pair<int,int> mx = {-1,-1};
            for(int i = bb.nd.st;i <= bb.nd.nd;i++)
            {
                cout<<"?"<<" "<<mid<<" "<<i<<" "<<1<<endl;
                int c;
                cin>>c;
                debug();
                if(mx.st < c)
                {
                    mx.st = c;
                    mx.nd = i;
                }
                if(tmx.st < c)
                {
                    tmx.st = c;
                    tmx.nd.st = mid;
                    tmx.nd.nd = i;
                }
            }
            int m1 = -1,m2 = -1;
            if(mid != 1)
            {
                cout<<"? "<<mid-1<<" "<<mx.nd<<" "<<1<<endl;
                cin>>m1;
                debug();
                if(tmx.st < m1)
                {
                    tmx.st = m1;
                    tmx.nd.st = mid-1;
                    tmx.nd.nd = mx.nd;
                }
            }
            if(mid != n)
            {
                cout<<"? "<<mid+1<<" "<<mx.nd<<" "<<1<<endl;
                cin>>m2;
                debug();
                if(tmx.st < m2)
                {
                    tmx.st = m2;
                    tmx.nd.st = mid+1;
                    tmx.nd.nd = mx.nd;
                }
            }
            
            if(mx.st > m1 && mx.st > m2)
            {
                cout<<"! "<<mid<<" "<<mx.nd<<" "<<1<<endl;
                return 0;
            }
            if(tmx.nd.st > mid)
            {
                bb.st.st = mid + 1;
            }
            else
            {
                bb.st.nd = mid - 1;
            }
        }
        else
        {
            int mid = (bb.nd.st+bb.nd.nd)/2;
            pair<int,int> mx = {-1,-1};
            for(int i = bb.st.st;i <= bb.st.nd;i++)
            {
                cout<<"?"<<" "<<i<<" "<<mid<<" "<<1<<endl;
                int c;
                cin>>c;
                debug();
                if(mx.st < c)
                {
                    mx.st = c;
                    mx.nd = i;
                }
                if(tmx.st < c)
                {
                    tmx.st = c;
                    tmx.nd.st = i;
                    tmx.nd.nd = mid;
                }
            }
            int m1 = -1,m2 = -1;
            if(mid != 1)
            {
                cout<<"? "<<mx.nd<<" "<<mid-1<<" "<<1<<endl;
                cin>>m1;
                debug();
                if(tmx.st < m1)
                {
                    tmx.st = m1;
                    tmx.nd.st = mx.nd;
                    tmx.nd.nd = mid-1;
                }
            }
            if(mid != m)
            {
                cout<<"? "<<mx.nd<<" "<<mid+1<<" "<<1<<endl;
                
                cin>>m2;
                debug();
                if(tmx.st < m2)
                {
                    tmx.st = m2;
                    tmx.nd.st = mx.nd;
                    tmx.nd.nd = mid+1;
                }
            }
            if(mx.st > m1 && mx.st > m2)
            {
                cout<<"! "<<mx.nd<<" "<<mid<<" "<<1<<endl;
                return 0;
            }
            if(tmx.nd.nd > mid)
            {
                bb.nd.st = mid + 1;
            }
            else
            {
                bb.nd.nd = mid - 1;
            }
        }
    }
    cout<<"! "<<bb.st.st<<" "<<bb.nd.st<<" "<<1<<endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 22
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 14
• Subtask 6: 0 / 23