QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#608042#8939. PermutationzzlWA 1ms3608kbC++17731b2024-10-03 18:02:402024-10-03 18:02:41

Judging History

This is the latest submission verdict.

  • [2024-10-03 18:02:41]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3608kb
Show
  • [2024-10-03 18:02:40]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,l,r;
int qu(int l,int r) {
    cout<<'?'<<' '<<l<<' '<<r<<endl;
    cout.flush();
    int tem;
    cin>>tem;
    return tem;
}
int work(int l,int r,int s) {
    if(l==r)return l;
    if(s==0)s=qu(l,r);
    if(l==r-1)return s==l?r:l;
       if(r-s>=s-l) {int mid=l+(0.6*(r-l));
        if(qu(l,mid)==s)return work(l,mid,s);
        else return work(mid+1,r,0);
    }
    else {int mid=r-(0.6*(r-l));
        if(qu(mid,r)==s)return work(mid,r,s);
        else return work(l,mid-1,0);
    }
}
signed main() {
    int t;
    cin>>t;
    while(t--) {
        cin>>n;
        n=work(1,n,0);
        cout<<'!'<<' '<<n<<endl;
    }
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3608kb

input:

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

output:

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

result:

ok Correct (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3604kb

input:

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

output:

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

result:

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

Server Time: 2025-02-09 10:57:48 | OpenSource Project