QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#453835#8819. CNOI Knowledgeucup-team3699WA 31ms10600kbC++231.4kb2024-06-24 12:41:182024-06-24 12:41:18

Judging History

你现在查看的是最新测评结果

  • [2024-06-24 12:41:18]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:10600kb
  • [2024-06-24 12:41:18]
  • 提交

answer

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

#define int long long
#define F first 
#define S second
#define pb push_back

const int mol=998244353;

int ans1[1005][1005];
int cnt=0;

int get(int l, int r){
    if(l==r) return 1;
    if(ans1[l][r]==0){
        cout<<"? "<<l<<" "<<r<<endl;
        int iu;
        cin>>iu;
        ans1[l][r]=iu;
        return iu;
    }
    else return ans1[l][r];
}

void solve(){
    int n;
    cin>>n;
    bool ok=1;
    vector<int>ans(n+1);
    int iu=2;
    for(int i=1;i<=n;i++){
        if(i==1){
            ans[i]=1;
            continue;
        }
        if(get(1, i)-get(1, i-1)==i) {
            ans[i]=iu++;
            continue;
        }

        int l=1, r=i;
        for(int j=1;j<i;j++){
            if(r<j) break;
            if(ans1[j][i-1]){
                if(get(j, i) - get(j, i-1) == i-j+1) r=j;
                else l=j+1;
            }
        }
        
        while(l<r){
            int mid=l+r>>1;
            if(get(mid, i) - get(mid, i-1) == i-mid+1) r=mid;
            else l=mid+1;
        }
        if(l==1) ans[i]=iu++;
        else ans[i]=ans[l-1];
    }

    cout<<"! ";
    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";cout<<endl;
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    // int t;
    // cin>>t;
    // while(t--)
    solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

12
3
6
10
15
21
27
10
6
15
10
20
15
34
26
20
14
6
3
9
6
43
52
14
10
5
3
2
62
19
8
5
72
25
13
19
13

output:

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

result:

ok Accepted. 36 queries used.

Test #2:

score: -100
Wrong Answer
time: 31ms
memory: 10600kb

input:

1000
3
5
2
7
3
2
11
7
16
11
5
3
2
21
15
7
3
2
27
21
11
7
34
27
15
11
5
3
3
41
33
19
15
8
5
2
48
39
23
19
11
7
3
2
57
47
29
24
14
9
4
3
2
66
55
35
29
17
11
5
4
3
2
75
63
41
34
20
13
6
5
4
3
2
84
71
47
39
23
15
7
6
5
4
3
2
96
82
56
47
31
23
15
108
93
65
55
39
31
23
11
7
5
3
3
124
108
78
67
49
40
31
15...

output:

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

result:

wrong answer Too many queries.