제출 #723685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
723685		The_Samurai	Worm Worries (BOI18_worm)	C++17	0 / 100	92 ms	4176 KiB

worm

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
int INF = 2e9;

int ask(int n, int m = 1, int k = 1) {
    int ans;
    cout << "? " << n << ' ' << m << ' ' << k << endl;
    cin >> ans;
    return ans;
}

void out(int n, int m = 1, int k = 1) {
    cout << "! " << n << ' ' << m << ' ' << k << endl;
    ::exit(0);
}

void solve() {
    int n, m, k, q;
    cin >> n >> m >> k >> q;
    if (max(m, k) == 1) {
        int lx = 1, rx = n;
        vector<int> ans(n + 2, -1);
        ans[1] = ask(1);
        q--;
        ans[0] = ans[n + 1] = 0;
        while (rx - lx > 3) {
            int mid = (lx + rx) >> 1;
            if (ans[mid] == -1) {
                ans[mid] = ask(mid);
                q--;
            }
            if (ans[mid] - ans[lx] < mid - lx) {
                rx = mid;
            } else {
                lx = mid;
            }
        }
        for (int i = max(1, lx - 1); i <= min(n, rx + 1); i++) {
            if (ans[i] == -1) {
                ans[i] = ask(i);
                q--;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (ans[i] == -1 and q > 0) {
                ans[i] = ask(i);
                q--;
            }
            if (min(ans[i - 1], min(ans[i], ans[i + 1])) != -1) {
                if (max(ans[i - 1], ans[i + 1]) <= ans[i]) {
                    out(i);
                }
            }
        }

    }
}

int main() {
    ::srand(::time(0));
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);

    int queries = 1;
#ifdef test_cases
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
//    cin >> queries;
#else
    //    cin >> queries;
#endif

    for (int test_case = 1; test_case <= queries; test_case++) {
        solve();
//        cout << '\n';
    }
}

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