QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488942#8819. CNOI KnowledgeMathew_MiaoWA 51ms3980kbC++233.0kb2024-07-24 16:32:142024-07-24 16:32:14

Judging History

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

  • [2024-07-24 16:32:14]
  • 评测
  • 测评结果:WA
  • 用时:51ms
  • 内存:3980kb
  • [2024-07-24 16:32:14]
  • 提交

answer

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e3+10;
const int N=1e3;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
int n,m,cnt=0;
int a[MAXN],s[MAXN];
namespace SA{
    int cnt;
    int sa[MAXN],h[MAXN];
    int rnk[MAXN<<1],lst[MAXN<<1];
    int sum[MAXN],id[MAXN];
    inline void build(){
        cnt=n;
        for(int i=1;i<=m;i++)
        {
            rnk[i]=s[i];
        }
        #define cnt_sort(sth) {\
            memset(sum,0,sizeof(int)*(cnt+1));\
            for(int i=1;i<=m;i++)\
            {\
                sum[rnk[sth]]++;\
            }\
            for(int i=1;i<=cnt;i++)\
            {\
                sum[i]+=sum[i-1];\
            }\
            for(int i=m;i;i--)\
            {\
                sa[sum[rnk[sth]]]=sth;\
                sum[rnk[sth]]--;\
            }\
        }
        cnt_sort(i);
        for(int w=1;w<=m;w<<=1)
        {
            for(int i=1;i<=w;i++)
            {
                id[i]=m-w+i;
            }
            int now=w;
            for(int i=1;i<=m;i++)
            {
                if(sa[i]>w){
                    now++;
                    id[now]=sa[i]-w;
                }
            }
            cnt_sort(id[i]);
            cnt=0;
            memcpy(lst,rnk,sizeof(int)*(m+1));
            for(int i=1;i<=m;i++)
            {
                if((lst[sa[i]]^lst[sa[i-1]])||(lst[sa[i]+w]^lst[sa[i-1]+w])){
                    cnt++;
                }
                rnk[sa[i]]=cnt;
            }
            if(cnt==m){
                break;
            }
        }
        int k=0;
        for(int i=2;i<=m;i++)
        {
            if(k){
                k--;
            }
            while(s[i+k]==s[sa[rnk[i]-1]+k])
            {
                k++;
            }
            h[rnk[i]]=k;
        }
    }
}
inline int query(int l,int r){
    if(!a[r]){
        printf("? %d %d\n",l,r);
        fflush(stdout);
        int res;
        scanf("%d",&res);
        return res;
    }
    m=r-l+1;
    memcpy(s+1,a+l,sizeof(int)*m);
    s[m+1]=0;
    SA::build();
    int res=m*(m+1)>>1;
    for(int i=1;i<=m;i++)
    {
        res-=SA::h[i];
    }
    return res;
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int l=0,r=i-1,mid;
        while(l<r)
        {
            mid=(l+r+1)>>1;
            if((query(mid,i)-query(mid,i-1))^(i-mid+1)){
                l=mid;
            }
            else{
                r=mid-1;
            }
        }
        if(!l){
            cnt++;
            a[i]=cnt;
        }
        else{
            a[i]=a[l];
        }
    }
    putchar('!');
    putchar(' ');
    for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    putchar('\n');
    fflush(stdout);
    return 0;
}

詳細信息

Test #1:

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

input:

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

output:

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

result:

ok Accepted. 27 queries used.

Test #2:

score: -100
Wrong Answer
time: 51ms
memory: 3980kb

input:

1000
3
5
2
3
2
7
5
8
5
11
3
2
11
5
7
15
27
21
15
8
5
19
7
3
2
19
4
3
2
23
5
3
2
20
5
3
2
23
5
3
2
23
9
13
11
31
14
8
5
31
15
7
11
41
16
8
5
45
15
7
11
55
20
7
15
11
58
21
8
5
68
21
8
5
69
21
8
5
80
26
12
5
8
79
24
12
5
8
89
24
12
5
8
87
26
11
5
8
100
32
11
5
8
100
31
11
5
8
112
31
12
5
8
111
31
11
3...

output:

? 1 2
? 1 3
? 2 3
? 2 4
? 3 4
? 2 5
? 3 5
? 3 6
? 4 6
? 3 7
? 5 7
? 6 7
? 4 8
? 6 8
? 5 8
? 4 9
? 2 9
? 3 9
? 5 10
? 7 10
? 8 10
? 5 11
? 8 11
? 9 11
? 10 11
? 6 12
? 9 12
? 10 12
? 11 12
? 6 13
? 9 13
? 11 13
? 12 13
? 7 14
? 10 14
? 12 14
? 13 14
? 7 15
? 11 15
? 13 15
? 14 15
? 8 16
? 12 16
? 10 ...

result:

wrong answer Wrong Answer.