Submission #311697

#	Time	Username	Problem	Language	Result	Execution time	Memory
311697		OttoTheDino	Worm Worries (BOI18_worm)	C++17	10 / 100	1 ms	384 KiB

worm

#include <bits/stdc++.h>
using namespace std;

#define rep(n)      for (int i = 0; i < n; ++i)
#define rep2(n)     for (int j = 0; j < n; ++j)
#define mp          make_pair
#define pb          push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;

int get (int id) {
    int num;
    cout << "? " << id << " 1 1\n" << flush;
    cin >> num;
    return num;
}

int main() {    
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m, k, q;
    map<int, int> a;
    cin >> n >> m >> k >> q;
    
    if (n==1) {
        cout << "1 1 1\n" << flush;
        return 0;
    }
    
    int lo = 1, hi = n-1;
    while (lo<hi) {
        int mid = (lo+hi)/2;
        if (a[mid]==0) a[mid] = get(mid);
        if (a[mid+1]==0) a[mid+1] = get(mid+1);
        if (a[mid+1]>a[mid]) lo = mid+1;
        else hi = mid-1;
    }
    
    if (a[lo]==0) a[lo] = get(lo);
    if (a[lo+1]==0) a[lo+1] = get(lo+1);
    
    cout << "! " << (a[lo]>a[lo+1]?lo:lo+1) << " 1 1\n" << flush;
    
    return 0;
}

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