QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#682720#8819. CNOI KnowledgeRainingLoveWA 49ms4608kbC++231.1kb2024-10-27 17:04:392024-10-27 17:04:39

Judging History

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

  • [2024-10-27 17:04:39]
  • 评测
  • 测评结果:WA
  • 用时:49ms
  • 内存:4608kb
  • [2024-10-27 17:04:39]
  • 提交

answer

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

int n;
int sameTo[10003];
int ans[10003];

map<pair<int,int>,int> mp;
int ask(int l,int r) {
    if(mp.find({l,r})!=mp.end()) return mp[{l,r}];
    cout<<"? "<<l<<" "<<r<<endl;
    int d;
    cin>>d;
    return mp[{l,r}]=d;
}
void solve() {
    cin>>n;
    for(int i=2;i<=n;i++) {
        int l=1,r=i-1;
        int ans=0;
        while(l<=r) {
            int mid=l+r>>1;
            if(ask(mid,i-1)+(i-1-mid+1)+1==ask(mid,i)) {
                r=mid-1;
            }
            else {
                ans=mid;//mid到i,i不是第一次出现
                l=mid+1;
            }
        }
        sameTo[i]=ans;
    }

    int c=0;
    for(int i=1;i<=n;i++) {
        if(sameTo[i]) ans[i]=ans[sameTo[i]];
        else ans[i]=++c;
    }

    cout<<"! ";
    for(int i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }cout<<endl;
}
/*
1 2 3 3
*/
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    int t=1;
    // cin>>t;
    while(t--)
    solve();
}

詳細信息

Test #1:

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

input:

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

output:

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

result:

ok Accepted. 42 queries used.

Test #2:

score: -100
Wrong Answer
time: 49ms
memory: 4608kb

input:

1000
1
3
5
1
2
3
1
2
7
7
11
5
8
3
5
1
2
11
3
1
2
7
11
5
7
15
8
3
5
1
3
11
15
8
5
1
2
19
7
3
1
2
15
19
4
3
1
2
23
5
3
1
2
17
20
4
5
3
1
2
23
4
5
3
1
2
15
23
4
9
6
13
7
15
31
14
5
8
3
5
1
3
23
31
11
15
7
5
1
3
41
11
16
8
5
1
2
36
45
11
15
7
3
1
2
55
20
7
11
15
11
48
58
21
5
8
3
5
1
2
68
16
21
8
5
59
6...

output:

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

result:

wrong answer Too many queries.