제출 #1260029

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260029		Szymon_Pilipczuk	Worm Worries (BOI18_worm)	C++20	10 / 100	8 ms	408 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(int k)
{
    if(k == -1)
    {
        exit(0);
    }
    c++;
    if(c > q)
    {
        exit(0);
    }
}
int main()
{
    cin>>n>>m>>k>>q;
    pair<int,int> bb[2];
    bb[0] = {1,n};
    bb[1] = {1,m};
    pair<int,pair<int,int>> tmx = {-1,{-1,-1}};
    while(bb[0].st < bb[0].nd || bb[1].st < bb[1].nd)
    {
        cerr<<bb[0].st<<" "<<bb[0].nd<<" "<<bb[1].st<<" "<<bb[1].nd<<"\n";
        bool w;
        if(bb[0].nd - bb[0].st > bb[1].nd - bb[1].st)
        {
            w = 0; 
        }
        else
        {
            w = 1;
        }
        int mid = (bb[w].st+bb[w].nd)/2;
        pair<int,int> mx = {-1,-1};
        for(int i = bb[w^1].st;i <= bb[w^1].nd;i++)
        {
            if(w == 0)cout<<"?"<<" "<<mid<<" "<<i<<" "<<1<<endl;
            else cout<<"?"<<" "<<i<<" "<<mid<<" "<<1<<endl;
            int c;
            cin>>c;
            debug(c);
            if(mx.st < c)
            {
                mx.st = c;
                mx.nd = i;
            }
            if(tmx.st < c)
            {
                tmx.st = c;
                if(w == 0)
                {
                    tmx.nd.st = mid;
                    tmx.nd.nd = i;
                }
                else
                {

                    tmx.nd.st = i;
                    tmx.nd.nd = mid;
                }
            }
        }
        int m1 = -1,m2 = -1;
        if(mid > 1)
        {
            if(w == 0)cout<<"?"<<" "<<mid-1<<" "<<mx.nd<<" "<<1<<endl;
            else cout<<"?"<<" "<<mx.nd<<" "<<mid-1<<" "<<1<<endl;
            cin>>m1;
            debug(m1);
            if(tmx.st < m1)
            {
                tmx.st = m1;
                if(w == 0)
                {
                    tmx.nd.st = mid-1;
                    tmx.nd.nd = mx.nd;
                }
                else
                {

                    tmx.nd.st = mx.nd;
                    tmx.nd.nd = mid-1;
                }
            }
        }
        if((w == 0 && mid < n) || (w && mid < m))
        {
            if(w == 0)cout<<"?"<<" "<<mid+1<<" "<<mx.nd<<" "<<1<<endl;
            else cout<<"?"<<" "<<mx.nd<<" "<<mid+1<<" "<<1<<endl;
            cin>>m2;
            debug(m2);
            if(tmx.st < m2)
            {
                tmx.st = m2;
                if(w == 0)
                {
                    tmx.nd.st = mid+1;
                    tmx.nd.nd = mx.nd;
                }
                else
                {

                    tmx.nd.st = mx.nd;
                    tmx.nd.nd = mid+1;
                }
            }
        }        
        if(mx.st > m1 && mx.st > m2)
        {
            if(w ==0 ) cout<<"! "<<mid<<" "<<mx.nd<<" "<<1<<endl;
            else cout<<"! "<<mx.nd<<" "<<mid<<" "<<1<<endl;
            return 0;
        }
        
        if((w == 0 && tmx.nd.st > mid || w == 1 && tmx.nd.nd > mid)) 
        {
            bb[w].st = mid + 1;
        }
        else
        {
            bb[w].nd = mid - 1;
        }
        
    }
    cout<<"! "<<bb[0].st<<" "<<bb[1].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