Submission #1259952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259952		Szymon_Pilipczuk	Worm Worries (BOI18_worm)	C++20	32 / 100	0 ms	408 KiB

worm

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
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;
ld phi =((ld)3 -sqrt(5))/2;
int fgs(int ize)
{
    return ize * phi;
}
int main()
{
    int n,m,k,q;
    cin>>n>>m>>k>>q;
    pair<int,int> ran = {1,n};
    int ize = ran.nd - ran.st + 1;
    int l;
    cout<<"?"<<" "<<ran.st + fgs(n)<<" "<<1<<" "<<1<<endl;
    cin>>l;
    int r;
    bool prev = 0;
    while(ran.st + 2 < ran.nd)
    {
        if(prev)
        {
            cout<<"?"<<" "<<ran.st + fgs(ize)<<" "<<1<<" "<<1<<endl;
            cin>>l;
        }
        else
        {
            cout<<"?"<<" "<<ran.nd -  fgs(ize)<<" "<<1<<" "<<1<<endl;
            cin>>r;
        }
        //cerr<<fgs(ize)<<" "<<l<<" "<<r<<"\n";
        if(l > r)
        {
            ran.nd -= fgs(ize) + 1;
            prev = true;
            r = l;
            ize = ran.nd - ran.st + 1;
        }
        else
        {
            ran.st += fgs(ize) + 1;
            prev = false;
            l = r;
            ize = ran.nd - ran.st + 1;
        }
        //cerr<<ran.st<<" "<<ran.nd<<"\n";
        
    }
    pair<int,int> mx = {-1,-1};
    for(int i = ran.st;i<= ran.nd;i++)
    {
        cout<<"?"<<" "<<i<<" "<<1<<" "<<1<<endl;
        int c;
        cin>>c;
        if(c > mx.st)
        {
            mx.st = c;
            mx.nd = i;
        }
    }
    cout<<"!"<<" "<<mx.nd<<" "<<1<<" "<<1<<"\n";
    
}

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