QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#40499#1425. DivCrysflyTL 277ms3736kbC++111.7kb2022-07-22 12:28:142022-07-22 12:28:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-22 12:28:16]
  • 评测
  • 测评结果:TL
  • 用时:277ms
  • 内存:3736kb
  • [2022-07-22 12:28:14]
  • 提交

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
...

result: