QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#554081	#8939. Permutation	Charizard2021	ML	1ms	3720kb	C++14	1.6kb	2024-09-09 05:05:21	2024-09-09 05:05:21

Judging History

This is the latest submission verdict.

[2024-09-09 05:05:21]
Judged

Verdict: ML
Time: 1ms
Memory: 3720kb

Show

[2024-09-09 05:05:21]
Submitted

answer

#include<bits/stdc++.h>
using namespace std;
long double phi = (sqrt(5.0) - 1.0)/2.0;
int solve(int low, int high, int cur){
    if(low == high){
        return low;
    }
    if(cur == INT_MIN){
        cout << "? " << low << " " << high << "\n";
        cout.flush();
        cin >> cur;
    }
    if(low + 1 == high){
        if(cur == low){
            return high;
        }
        else{
            return low;
        }
    }
    int val = (int)((long double)(high - low + 1) * (long double)phi + (long double)0.5);
    int mid;
    if(cur <= val + low){
        mid = val + low;
    }
    else{
        mid = high - val;
    }
    if(cur <= mid){
        int x = INT_MIN;
        if(low != mid){
            cout << "? " << low << " " << mid << "\n";
            cout.flush();
            cin >> x;
        }
        if(x == cur){
            return solve(low, mid, x);
        }
        else{
            return solve(mid + 1, high, INT_MIN);
        }
    }
    else{
        int x = INT_MIN;
        if(mid + 1 != high){
            cout << "? " << mid + 1 << " " << high << "\n";
            cout.flush();
            cin >> x;
        }
        if(x == cur){
            return solve(mid + 1, high, x);
        }
        else{
            return solve(low, mid, INT_MIN);
        }
    }
}
int main(){
    // cout << fixed << setprecision(9) << phi << "\n";
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int res = solve(1, n, INT_MIN);
        cout << "! " << res << "\n";
        cout.flush();
    }
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3720kb

input:

output:

result:

ok Correct (3 test cases)

Test #2:

score: -100

Memory Limit Exceeded

input:

output: