제출 #680574

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680574		Cross_Ratio	Worm Worries (BOI18_worm)	C++14	0 / 100	1 ms	208 KiB

worm

#include <bits/stdc++.h>
using namespace std;
map<array<int, 3>, int> M;
int query_cnt = 0;
int query(int a, int b, int c) {
    if(M.count({a, b, c})) return M[{a, b, c}];
    query_cnt++;
    cout << "? " << a << ' ' << b << ' ' << c << endl;
    int d;
    cin >> d;
    M[{a, b, c}] = d;
    return d;
}
void answer(int a, int b, int c) {
    cout << "! " << a << ' ' << b << ' ' << c << endl;
    return;
}
int fibo[44];
void subtask_12() {
    int N = fibo[30];
    int s = 1, e = N;
    int x = fibo[28], y = fibo[29];
    while(s<=e) {
        if(s==e) {
            answer(s, 1, 1);
            return;
        }
        if(s+1==e) {
            if(query(s, 1, 1) >= query(e, 1, 1)) {
                answer(s, 1, 1);
                return;
            }
            else {
                answer(e, 1, 1);
                return;
            }
        }
        if(s+3>=e) {
            int mid = (s + e + 1) / 2;
            if(query(mid, 1, 1) < query(mid+1, 1, 1)) {
                s = mid + 1;
            }
            else {
                e = mid;
            }
            continue;
        }
        if((x<=N?query(x, 1, 1):-1) > (y <= N ? query(y, 1, 1) : -1)) {
            e = y;
            y = x;
            x = (s+e) - y;
        }
        else {
            s = x;
            x = y;
            y = (s+e) - x;
        }
    }
}
void subtask_34() {

}
void subtask_56() {

}
signed main() {
    fibo[0] = fibo[1] = 1;
    for(int i = 2 ; i <= 43; i++) {
        fibo[i] = fibo[i-1] + fibo[i-2];
        //cout << i << " : " << fibo[i] << '\n';
    }
    int N, M, K, Q;
    cin >> N >> M >> K >> Q;
    if(M==1 && K == 1 && N == 1000000) {
        subtask_12();
    }
    if(K==1 && N==M) {
        subtask_34();
    }
    if(K==N && K==M) {
        subtask_56();
    }
    //cout << query_cnt;
}

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