Submission #469821

#	Time	Username	Problem	Language	Result	Execution time	Memory
469821		Ozy	Worm Worries (BOI18_worm)	C++17	32 / 100	1 ms	200 KiB

worm

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 1000000

lli n,m,k,q,res,x;

double phi = (1+sqrt(5))/2;

lli query(lli pos) {

    if (pos > n || pos == 0) return 0;

    cout << "? " << pos << " 1 1" << endl;

    lli a;
    cin >> a;
    if (a == -1) exit(0);
    return a;
}

lli gold(lli ini, lli fin){
    lli val = ini + (fin-ini+1)/phi;
    return val;
}

lli busca(lli ini, lli fin, lli x, lli vx) {

    if (ini==fin) return x;

    lli y = gold(ini,fin);
    if (2*x > ini+fin) y = (ini+fin) - y;
    if (x == y) y++;

    lli vy = query(y);
    if (x > y) {swap(x,y); swap(vx,vy);}

    if (vx >= vy) return busca(ini,y-1,x,vx);
    else return busca(x+1,fin,y,vy);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> k >> q;
    res = 0;

    x = gold(1,n);
    res = busca(1,n,x,query(x));

    cout << "! " << res << " 1 1";
}

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