QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#96543#1425. Divcatalyst_testWA 5ms3464kbC++142.5kb2023-04-14 11:22:462023-04-14 11:22:48

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-14 11:22:48]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3464kb
  • [2023-04-14 11:22:46]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using i64=long long;
using u64=unsigned long long;
using db=double;
using pii=pair<int,int>;
using vi=vector<int>;

template<typename T>
inline T read(){
    T x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) x=x*10+(ch-'0'),ch=getchar();
    return f?-x:x;
}

#define rdi read<int>
#define rdi64 read<i64>
#define fi first
#define se second
#define pb push_back

const int N=1e5+10,L=21;

int n,m;

int pos[N*L*2],v[N*L*2],tot;
int _cnt[N*4],*cnt=_cnt+N*2;
pii val[N*2];int tot1;

void modify(int x,int to){
    --cnt[v[x]],++cnt[v[x]=to];
}

// Precondition: p > 1, m > 1
bool check(int p){
    static pii st[N*2];int tp=0;
    queue<int> q;
    for(int i=tot1-1;i>=0;i--){
        if(abs(val[i].se)>=p) q.push(val[i].fi);
        else break;
    }
    while(!q.empty()){
        int x=q.front();q.pop();
        if(abs(v[x])<p) continue;
        int nx=(x+1)%tot;
        st[++tp]={x,v[x]},st[++tp]={nx,v[nx]};
        modify(nx,v[nx]+v[x]/p),modify(x,v[x]%p);
        if(abs(v[nx])>=p) q.push(nx);
    }
    bool ret=(cnt[-p+1]==m||cnt[0]==tot||cnt[p-1]==m);
    while(tp){
        int x=st[tp].fi,y=st[tp].se;
        --cnt[v[x]],++cnt[v[x]=y],--tp;
    }
    return ret;
}

void clear(){
    for(int i=0;i<tot;i++)
        cnt[v[i]]=0,v[i]=0;
    tot=0;
}

void solve(){
    n=rdi(),m=rdi();
    i64 sum1=0;
    for(int i=0;i<n;i++){
        int b=rdi(),a=rdi();
        sum1+=b,val[i*2]={(a+1)%m,b},val[i*2+1]={a%m,-b};
    }
    if(m==1) {puts("-1");return;}
    n*=2;int len=__lg(n);
    sort(val,val+n),tot=0;
    for(int i=0,p=0;i<m;){
        while(p<n&&val[p].fi<=i) ++p;
        if(m+i-val[(p+n-1)%n].fi<=len)
            pos[tot++]=i++;
        else if(p<n) i=val[p].fi;
        else break;
    }
    tot1=0;
    for(int l=0,r,j=0;l<n;l=r){
        while(pos[j]<val[l].fi) ++j;
        r=l;int sum=0;
        while(r<n&&val[l].fi==val[r].fi)
            sum+=val[r++].se;
        val[tot1++]={j,v[j]=sum};
    }
    for(int i=0;i<tot;i++)
        ++cnt[v[i]];
    sort(val,val+tot1,[&](pii a,pii b){
        return abs(a.se)<abs(b.se);
    });
    int ans=0;
    if(cnt[0]==tot) ans=-1;
    else{
        if(sum1%m==0) ++ans;
        for(int i=2;i<=n+1;i++)
            ans+=check(i);
    }
    cout<<ans<<'\n';
    clear();
}

int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    int T=rdi();
    while(T--) solve();
    return 0;
}

詳細信息

Test #1:

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

input:

3
5 2
1 0
1 0
1 0
1 0
1 0
5 3
-1 2
-1 1
-1 0
1 1
-1 1
12 3
-1 0
-1 7
1 8
1 8
-1 4
-1 6
1 8
1 2
1 5
1 2
-1 9
1 5

output:

1
-1
2

result:

ok 3 number(s): "1 -1 2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3464kb

input:

1
1 1
1 0

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: -100
Wrong Answer
time: 5ms
memory: 3364kb

input:

4
1 1000000000
1 0
1 1
1 1000000000
1 1000000000
-1 0
1 1
-1 1000000000

output:

-1
-1
-1
-1

result:

wrong answer 1st numbers differ - expected: '0', found: '-1'