QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#40499 | #1425. Div | Crysfly | TL | 277ms | 3736kb | C++11 | 1.7kb | 2022-07-22 12:28:14 | 2022-07-22 12:28:16 |
Judging History
answer
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 200005
#define inf 0x3f3f3f3f
int n,m;
map<int,int>a,aa;
set<pii>s;
vi o;
void upd(int x,int y){o.pb(x);s.erase(mkp(a[x],x));s.insert(mkp(a[x]+=y,x));}
bool chk(int x)
{
while(s.size()){
if((s.begin())->fi<=-x){
int w=s.begin()->se;
upd(w,x);
upd((w+1)%m,-1);
}
else if((--s.end())->fi>=x){
int w=(--s.end())->se;
upd(w,-x);
upd((w+1)%m,1);
}
else break;
}
if(!s.size())return 1;
// a[i] 全相同 & a[i]=-x+1,0,x-1
if((s.begin()->fi)!=((--s.end())->fi))return 0;
if((s.begin()->fi)==0)return 1;
return s.size()==m && ((s.begin()->fi)==(x-1) || (s.begin()->fi)==(-x+1));
}
void clear(){
for(auto t:o)
s.erase(mkp(a[t],t)),s.insert(mkp(a[t]=aa[t],t));
o.clear();
}
void work()
{
n=read(),m=read(); a.clear(),s.clear();
int f1=0;
For(i,1,n){
int c=read(),x=read();
a[x%m]-=c,a[(x+1)%m]+=c,f1+=c;
}
int res=(f1%m==0);
bool all0=1;
for(auto t:a){
if(t.se){
all0=0;
aa[t.fi]=t.se;
s.insert(mkp(t.se,t.fi));
}
}
a=aa;
if(all0){
puts("-1");
return;
}
For(i,2,n+1){
res+=chk(i);
clear();
}
cout<<res<<'\n';
}
signed main()
{
int T=read();
while(T--)work();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 3736kb
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: 3564kb
input:
1 1 1 1 0
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
4 1 1000000000 1 0 1 1 1 1000000000 1 1000000000 -1 0 1 1 -1 1000000000
output:
0 -1 0 -1
result:
ok 4 number(s): "0 -1 0 -1"
Test #4:
score: 0
Accepted
time: 277ms
memory: 3584kb
input:
100000 1 1 -1 0 1 1 1 0 1 1 -1 1 1 1 1 1 1 1 -1 2 1 1 1 2 1 1 -1 3 1 1 1 3 1 1 -1 4 1 1 1 4 1 1 -1 5 1 1 1 5 1 1 -1 6 1 1 1 6 1 1 -1 7 1 1 1 7 1 1 -1 8 1 1 1 8 1 1 -1 9 1 1 1 9 1 1 -1 10 1 1 1 10 1 1 -1 11 1 1 1 11 1 1 -1 12 1 1 1 12 1 1 -1 13 1 1 1 13 1 1 -1 14 1 1 1 14 1 1 -1 15 1 1 1 15 1 1 -1 16...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 24ms
memory: 3624kb
input:
50000 2 1 -1 0 -1 0 2 1 -1 0 1 0 2 1 -1 0 -1 1 2 1 -1 0 1 1 2 1 -1 0 -1 2 2 1 -1 0 1 2 2 1 -1 0 -1 3 2 1 -1 0 1 3 2 1 -1 0 -1 4 2 1 -1 0 1 4 2 1 -1 0 -1 5 2 1 -1 0 1 5 2 1 -1 0 -1 6 2 1 -1 0 1 6 2 1 -1 0 -1 7 2 1 -1 0 1 7 2 1 -1 0 -1 8 2 1 -1 0 1 8 2 1 -1 0 -1 9 2 1 -1 0 1 9 2 1 -1 0 -1 10 2 1 -1 0 ...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 50000 numbers
Test #6:
score: -100
Time Limit Exceeded
input:
100000 1 170035890 1 835589389 1 433027164 1 407537923 1 293860673 -1 788447900 1 838946623 1 450237482 1 629410117 1 476559978 1 171248763 1 671271287 1 468119514 1 346821429 1 112217885 -1 249186444 1 760504335 1 622839250 1 206432863 1 481956490 1 344167459 -1 251322298 1 603763257 -1 255443178 1...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...