QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#96543 | #1425. Div | catalyst_test | WA | 5ms | 3464kb | C++14 | 2.5kb | 2023-04-14 11:22:46 | 2023-04-14 11:22:48 |
Judging History
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'