QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#554083#8939. PermutationCharizard2021WA 5ms3628kbC++142.4kb2024-09-09 05:06:312024-09-09 05:06:32

Judging History

This is the latest submission verdict.

  • [2024-09-09 05:06:32]
  • Judged
  • Verdict: WA
  • Time: 5ms
  • Memory: 3628kb
Show
  • [2024-09-09 05:06:31]
  • 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;
        }
    }
    if(low + 2 == high){
        int mid = (low + high)/2;
        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 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: 3612kb

input:

3
5
3
3
2
6
6
3
1
4
3
2

output:

? 1 5
? 1 4
? 1 3
! 4
? 1 6
? 3 6
? 1 2
! 2
? 1 4
? 1 3
! 4

result:

ok Correct (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 5ms
memory: 3628kb

input:

10000
10
2
2
2
2
3
10
10
10
7
5
10
5
5
1
6
10
4
4
4
4
4
10
10
6
3
3
2
10
3
3
3
3
3

output:

? 1 10
? 1 7
? 1 5
? 1 4
? 1 3
! 4
? 1 10
? 5 10
? 7 10
? 5 6
! 6
? 1 10
? 1 7
? 1 5
? 6 7
! 7
? 1 10
? 1 7
? 1 5
? 1 4
? 3 4
! 3
? 1 10
? 5 10
? 1 4
? 1 3
? 1 2
! 1
? 1 10
? 1 7
? 1 5
? 1 4
? 1 3
? 1 2

result:

wrong answer Too many queries , n = 10 , now_q 6 (test case 6)
English 繁體中文 简体中文

Server Time: 2025-02-10 22:46:43 | OpenSource Project