请求加强数据/hack

AFLeartLey0103 @ 2022-07-13 11:38:07

by xfrvq @ 2022-07-13 11:39:37

@AFLeartLey 放个代码？

by AFLeartLey0103 @ 2022-07-13 11:49:37

@OneZzz6174

#include<bits/stdc++.h>
using namespace std;
int n,mm,x,pgy,a[40005],key[40005];
map<int,int>m;
void solve(int l,int r){
    int cnt[40005];memset(cnt,0,sizeof(cnt));
    for(int i=l;i<=r;i++){
        cnt[a[i]]++;
    }
    for(int i=1;i<=pgy;i++){
        if(cnt[i]>cnt[x] or (cnt[i]==cnt[x] and key[i]<key[x]))
            x=i;
    }
    x=key[x];
}
int main(){
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>mm;
    for(int i=1;i<=n;i++){
        cin>>x;
        map<int,int>::iterator it=m.find(x);
        if(it==m.end()){
            key[++pgy]=x;
            m.insert(pair<int,int>(x,pgy));
            a[i]=pgy;
            continue;
        }
        a[i]=it->second;
    }
    x=0;
    int l,r;
    for(int i=1;i<=mm;i++){
        cin>>l>>r;
        l=((l+x-1)%n)+1;
        r=((r+x-1)%n)+1;
        if(l>r)swap(l,r);
        x=0;
        solve(l,r);
        cout<<x<<endl;
    }
    return 0;
}

by AFLeartLey0103 @ 2022-07-13 11:53:07

@OneZzz6174

好像直接随机生成4e4个数卡map然后查五万次l=1 r=40000即可

by xfrvq @ 2022-07-13 11:54:22

@AFLeartLey 试试 map 换成这样的离散化会不会快一点？

    for(int i = 1;i <= n;++i) a[i] = b[i] = read();
    std::sort(b + 1,b + n + 1);
    tot = std::unique(b + 1,b + n + 1) - b - 1;
    for(int i = 1;i <= n;++i)
        a[i] = std::lower_bound(b + 1,b + tot + 1,a[i]) - b;

by AFLeartLey0103 @ 2022-07-13 11:58:52

@OneZzz6174

运行时间 3.37s

其实感觉这个能跑过还是比较扯 毕竟查询是O( r- l )的

by yukimianyan @ 2022-07-13 11:59:48

离散化只需要搞 4\times 10^4 个数，不用卡

for(int i=l;i<=r;i++){
    cnt[a[i]]++;
}

我觉得把这一段内存访问卡满（1,20001,2,20002,\cdots ,20000,40000）应该能卡

by xfrvq @ 2022-07-13 12:00:59

@AFLeartLey 等等，刚刚那个二分可以改成一个指针便利 b，复杂度可以在减去一个 \log

by AFLeartLey0103 @ 2022-07-13 12:01:58

@yukimianyan

我的做法是 随机生成4e4个数据查5e4次1 40000

如果写记忆化的话可以按长度从最长到最短查

by AFLeartLey0103 @ 2022-07-13 12:14:39

我造的hack数据下载在这里

by zyc2003 @ 2022-07-14 00:33:10

貌似 acwing 的数据过不了?

Click Here, 交一下试试