QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#682769#8819. CNOI KnowledgeRainingLoveWA 1ms3564kbC++231.4kb2024-10-27 17:18:202024-10-27 17:18:22

Judging History

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

  • [2024-10-27 17:18:22]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3564kb
  • [2024-10-27 17:18:20]
  • 提交

answer

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

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

map<pair<int,int>,ll> mp;
ll ask(int l,int r) {
    if(mp.find({l,r})!=mp.end()) return mp[{l,r}];
    cout<<"? "<<l<<" "<<r<<endl;
    ll d;
    cin>>d;
    return mp[{l,r}]=d;
}
void solve() {
    cin>>n;
    vector<int> firstShow;
    firstShow.push_back(1);
    ll last=1;
    v[1]=1;
    for(int i=2;i<=n;i++) {
        if(ask(1,i)==last+i) firstShow.push_back(i),v[i]=1;
    }
    for(int i=2;i<=n;i++) {
        if(v[i]) continue;
        int l=0,r=firstShow.size()-1;
        int ans=-1;
        while(l<=r) {
            int mid=l+r>>1;
            int now=firstShow[mid];
            if(ask(now,i-1)+(i-1-now+1)+1==ask(now,i)) {
                r=mid-1;
            }
            else {
                ans=mid;//mid到i,i不是第一次出现
                l=mid+1;
            }
        }
        if(ans==-1) continue;
        sameTo[i]=firstShow[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();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3564kb

input:

12
3
6
10
15
21
27
34
43
52
62
72
15
20
26
34
42
51
60

output:

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

result:

wrong answer Wrong Answer.