QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#542859#8939. Permutationucup-team2000#WA 6ms3652kbC++232.0kb2024-09-01 06:31:312024-09-01 06:31:58

Judging History

This is the latest submission verdict.

  • [2024-09-01 06:31:58]
  • Judged
  • Verdict: WA
  • Time: 6ms
  • Memory: 3652kb
Show
  • [2024-09-01 06:31:31]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

int query(int l, int r){
    if(r == l) return 0;
    cout << "? " << l << ' ' << r << endl;
    int pos;
    cin >> pos;
    return pos;
}

void solve(){
    int n;
    cin >> n;
    int l = 1, r = n;
    int pos = query(1, n);
    long double k = (-1 + sqrt(5)) / 2.0;
    while(l < r){
        if(l + 1 == r){
            if(pos == r) break;
            l = r;
            break;
        }
        if(l + 2 == r){
            if(l == pos){
                int uwu = query(l, l + 1);
                if(uwu == pos){
                    l = r = l + 1;
                }
                else{
                    l = r = l + 2;
                }
            }
            else if(l + 1 == pos){
                int uwu = query(l, l + 1);
                if(uwu == pos){
                    l = r = l;
                }
                else{
                    l = r = l + 2;
                }
            }
            else{
                int uwu = query(l + 1, l + 2);
                if(uwu == pos){
                    l = r = l + 1;
                }
                else{
                    l = r = l;
                }
            }
            break;
        }
        int mid = (l + r) / 2;
        if(pos >= mid){
            int md = (int)(r - (long double)(r - l) * k);
            md = max(md, l + 1);
            md = min(md, r - 1);
            int ree = query(md, r);
            if(ree == pos) l = md;
            else{
                pos = query(l, md - 1);
                r = md - 1;
            }
        }
        else{
            int md = (int)(l + (long double)(r - l) * k);
            md = max(md, l + 1);
            md = min(md, r - 1);
            int ree = query(l, md);
            if(ree == pos) r = md;
            else{
                pos = query(md + 1, r);
                l = md + 1;
            }
        }
    }
    cout << "! " << l << endl;
}

int main(){
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}
源文件, 语言: C++23

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3652kb

input:

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

output:

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

result:

ok Correct (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 6ms
memory: 3632kb

input:

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

output:

? 1 10
? 1 6
? 1 4
? 2 4
? 2 3
! 4
? 1 10
? 4 10
? 6 10
? 7 10
! 6
? 1 10
? 4 10
? 4 7
? 5 7
? 5 6
! 7
? 1 10
? 1 6
? 2 6
? 3 6
? 4 6
! 3
? 1 10
? 4 10
? 1 3
? 2 3
! 1
? 1 10
? 1 6
? 2 6
! 1
? 1 10
? 1 6
? 7 10
? 8 10
? 8 9
! 8
? 1 10
? 1 6
? 7 10
? 8 10
! 7
? 1 10
? 1 6
? 7 10
? 8 10
? 8 9
! 10
? 1...

result:

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

服务器时间: 2025-02-11 15:50:15 | 开源项目