QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#509341#6315. 填数游戏TheRaptor12 2922ms316228kbC++145.3kb2024-08-08 13:47:492024-08-08 13:47:49

Judging History

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

  • [2024-08-08 13:47:49]
  • 评测
  • 测评结果：12
  • 用时：2922ms
  • 内存：316228kb
查看
  • [2024-08-08 13:47:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
struct custom_hash {
    size_t operator()(pair<uint64_t,uint64_t> x) const {
        return (x.first<<21ll)+x.second;
    }
};
int n,m;
unordered_set<pair<int,int>,custom_hash> adj[1000005];
int bob[1000005],used[1000005],v[1000005],v2[1000005];
int pos[2][1000005][2],ans,tmp;
bool can;
void dfs(int x, int va, int p){
	if(used[x]!=-1){
		can=false;
		return;
	}
	bob[va]=x;
	used[x]=va;
	for(auto i:adj[x]){
		if(i.first==p) continue;
		dfs(i.first,i.second,x);
	}
}
pair<int,int> check(int x){
	pair<int,int> ret={1,(int)adj[x].size()};
	v[x]=1;
	for(auto i:adj[x]){
		if(v[i.first]) continue;
		pair<int,int> kid=check(i.first);
		ret.first+=kid.first;
		ret.second+=kid.second;
	}
	return ret;
}
vector<int> sing;
int key[1000005];
void keychain(int x){
	v2[x]=1; key[x]=1;
	if((int)adj[x].size()==1) sing.push_back(x);
	for(auto i:adj[x]){
		if(v2[i.first]) continue;
		keychain(i.first);
	}
}
vector<pair<int,pair<int,int> > > chain;
void getloop(int x, int p){
	key[x]=0;
	for(auto i:adj[x]){
		if(i.second==p) continue;
		chain.push_back({i.second,{x,i.first}});
		if(key[i.first]==0) continue;
		getloop(i.first,i.second);
		break;
	}
}
int subt[1000005],rev[1000005];
pair<int,int> revc[1000005];
void up(int x, int va){
	if(va>=revc[x].first){
		revc[x].second=revc[x].first;
		revc[x].first=va;
	}
	else if(va>revc[x].second) revc[x].second=va;
}
void pretree(int x, int p){
	subt[x]=0;
	revc[x]={0,0};
	for(auto i:adj[x]){
		if(i.first==p) continue;
		pretree(i.first,x);
		subt[x]+=subt[i.first];
		if(pos[0][i.second][0]==i.first||pos[0][i.second][1]==i.first){
			subt[x]++;
			up(x,rev[i.first]+1);
		}
		else if(pos[0][i.second][0]==x||pos[0][i.second][1]==x){
			up(x,rev[i.first]-1);
		}
		else up(x,rev[i.first]);
	}
	rev[x]=revc[x].first;
}
void rer(int x, int p){
	//cout << x << ' ' << subt[x] << ' ' << rev[x] << '\n';
	tmp=max(tmp,subt[x]-rev[x]);
	for(auto i:adj[x]){
		if(i.first==p) continue;
		subt[x]-=subt[i.first];
		if(pos[0][i.second][0]==i.first||pos[0][i.second][1]==i.first){
			subt[x]--;
			if(revc[x].first==rev[i.first]+1) rev[x]=revc[x].second;
		}
		else if(pos[0][i.second][0]==x||pos[0][i.second][1]==x){
			if(revc[x].first==rev[i.first]-1) rev[x]=revc[x].second;
		}
		else if(revc[x].first==rev[i.first]) rev[x]=revc[x].second;
		subt[i.first]+=subt[x];
		pair<int,int> org=revc[i.first];
		if(pos[0][i.second][0]==x||pos[0][i.second][1]==x){
			subt[i.first]++;
			up(i.first,rev[x]+1);
		}
		else if(pos[0][i.second][0]==x||pos[0][i.second][1]==x){
			up(i.first,rev[x]-1);
		}
		else up(i.first,rev[x]);
		rev[i.first]=revc[i.first].first;
		rer(i.first,x);
		
		subt[i.first]-=subt[x];
		if(pos[0][i.second][0]==x||pos[0][i.second][1]==x){
			subt[i.first]--;
		}
		revc[i.first]=org;
		rev[i.first]=revc[i.first].first;
		if(pos[0][i.second][0]==i.first||pos[0][i.second][1]==i.first){
			subt[x]++;
		}
		subt[x]+=subt[i.first];
		rev[x]=revc[x].first;
	}
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--){
		ans=0;
		cin >> n >> m;
		for(int i=0; i<=n; i++){
			bob[i]=-1;
			pos[0][i][0]=pos[0][i][1]=-1;
			pos[1][i][0]=pos[1][i][1]=-1;
		}
		for(int i=0; i<=m; i++) used[i]=-1;
		can=true;
		vector<pair<int,int> > sure;
		for(int i=0; i<2; i++){
			for(int j=0; j<n; j++){
				int num;
				cin >> num;
				for(int k=0; k<num; k++){
					cin >> pos[i][j][k];
				}
				if(i==1&&num==2){
					adj[pos[i][j][0]].insert({pos[i][j][1],j});
					adj[pos[i][j][1]].insert({pos[i][j][0],j});
				}
				else if(i==1) sure.push_back({j,pos[i][j][0]});
			}
		}
		for(auto i:sure) dfs(i.second,i.first,-1);
		if(!can){
			cout << -1 << '\n';
			continue;
		}
		for(int i=0; i<=m; i++) v[i]=0,v2[i]=0;
		for(int i=1; i<=m; i++){
			if(used[i]!=-1) continue;
			if(v[i]) continue;
			pair<int,int> lol=check(i);
			lol.second/=2;
			if(lol.second>lol.first) can=false;
			else if(lol.second==lol.first){
				sing.clear();
				keychain(i);
				while(!sing.empty()){
					int x=sing.back();
					sing.pop_back();
					pair<int,int> ed=*adj[x].begin();
					adj[x].clear();
					bob[ed.second]=x;
					used[x]=ed.second;
					adj[ed.first].erase({x,ed.second});
					if((int)adj[ed.first].size()==1) sing.push_back(ed.first);
				}
			}
			else{
				assert(lol.first==lol.second+1);
				tmp=0;
				pretree(i,-1);
				rer(i,-1);
				ans+=tmp;
			}
		}
		if(!can){
			cout << -1 << '\n';
			continue;
		}
		for(int i=1; i<=m; i++){
			if(key[i]){
				chain.clear();
				getloop(i,-1);
				int t1=0,t2=0,idk=0;
				for(auto [j,k]:chain){
					if((pos[0][j][0]==k.first||pos[0][j][0]==k.second)&&(pos[0][j][1]==k.first||pos[0][j][1]==k.second)){
						idk++;
					}
					else if(pos[0][j][0]==k.first||pos[0][j][1]==k.first){
						t1++;
					}
					else if(pos[0][j][0]==k.second||pos[0][j][1]==k.second){
						t2++;
					}
				}
				if(t1>t2) swap(t1,t2);
				int dif=min(t2-t1,idk);
				t1+=dif;
				idk-=dif;
				ans+=min(t1,t2)+idk/2;
			}
		}
		for(int i=0; i<n; i++){
			if(bob[i]!=-1){
				if(pos[0][i][0]==bob[i]||pos[0][i][1]==bob[i]) ans++;
			}
		}
		cout << ans << '\n';
		for(int i=0; i<=n; i++){
			bob[i]=-1;
		}
		for(int i=0; i<=m; i++){
			adj[i].clear();
			v[i]=v2[i]=key[i]=0;
		}
	}
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 78664kb

input:

20
9 10
2 5 2
2 4 3
1 3
2 4 10
2 1 7
2 1 2
2 5 3
1 6
2 2 7
2 5 4
2 4 3
2 3 9
2 10 4
2 3 1
2 1 2
2 8 7
2 2 6
2 2 7
9 10
2 2 5
2 2 8
2 7 2
2 4 7
2 6 7
2 10 9
2 9 3
2 5 7
2 1 5
2 2 1
2 8 7
2 7 10
2 4 3
2 6 5
2 9 8
2 2 3
2 6 7
2 5 4
9 10
2 2 7
2 4 10
2 5 6
2 2 6
2 9 8
2 7 5
2 3 6
2 6 3
2 7 6
2 7 8
2 5 4...

output:

4
0
3
1
1
1
8
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

wrong answer 9th numbers differ - expected: '9', found: '-1'

Test #2:

score: 0
Wrong Answer
time: 4ms
memory: 78712kb

input:

20
9 10
2 4 7
2 6 10
2 9 3
2 5 6
2 7 6
2 3 2
2 4 6
2 8 1
2 3 8
2 8 7
2 10 6
2 3 4
2 5 6
2 6 7
2 1 2
2 4 5
2 8 9
2 3 2
10 10
2 2 1
2 3 7
2 6 10
2 3 4
2 7 4
2 3 4
1 5
2 8 3
2 1 4
2 6 9
2 2 1
2 2 3
2 2 6
2 4 5
2 7 4
2 4 3
2 6 5
2 10 3
2 8 4
2 9 2
10 10
2 9 8
2 7 3
2 1 2
2 10 5
1 6
2 3 2
2 4 10
2 9 1
2 ...

output:

3
5
9
4
3
3
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

wrong answer 8th numbers differ - expected: '4', found: '-1'

Test #3:

score: 0
Wrong Answer
time: 4ms
memory: 78756kb

input:

20
10 10
1 5
2 3 6
2 4 3
2 2 9
2 1 2
2 4 10
2 4 6
2 7 8
2 2 4
2 3 2
2 5 6
2 2 6
2 3 4
2 2 9
2 1 2
2 10 4
2 4 7
2 8 7
2 5 4
2 2 3
9 10
2 5 8
1 2
2 2 6
2 10 3
1 4
2 9 8
1 10
2 7 8
2 5 3
2 7 8
2 1 2
2 6 5
2 2 3
2 4 3
2 8 9
2 5 10
2 7 6
2 5 4
9 10
2 9 5
2 10 2
2 1 9
2 1 8
2 5 10
1 8
1 4
2 4 6
2 1 10
2 1...

output:

6
1
4
4
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

wrong answer 6th numbers differ - expected: '3', found: '-1'

Test #4:

score: 0
Wrong Answer
time: 4ms
memory: 78364kb

input:

20
9 10
2 2 4
2 6 3
1 2
2 10 7
1 4
2 1 2
1 4
1 6
2 9 4
2 4 2
2 2 3
2 1 10
2 8 7
2 4 7
2 1 2
2 5 4
2 6 2
2 4 9
9 10
2 5 4
2 6 8
2 4 2
2 4 3
2 5 6
2 2 3
2 7 6
2 3 8
2 9 7
2 5 4
2 8 9
2 1 2
2 4 3
2 6 5
2 3 10
2 7 6
2 3 2
2 8 7
9 10
2 4 3
2 9 6
2 2 7
2 5 9
1 8
1 3
2 9 5
2 7 3
1 4
2 10 9
2 6 5
2 2 1
2 5 ...

output:

3
2
0
3
9
3
0
3
4
4
3
6
3
2
3
8
2
-1
-1
-1

result:

wrong answer 19th numbers differ - expected: '3', found: '-1'

Test #5:

score: 0
Wrong Answer
time: 14ms
memory: 77220kb

input:

20
10 10
2 7 3
2 6 2
1 3
2 1 4
2 3 4
1 1
2 5 4
2 1 8
1 4
2 4 8
2 7 6
2 3 2
2 8 3
2 10 4
2 5 4
2 6 1
2 5 6
2 1 2
2 9 4
2 4 3
10 10
2 2 1
1 4
2 10 3
2 2 4
1 6
2 5 9
2 6 9
1 2
2 3 8
1 2
2 2 10
2 8 4
2 4 3
2 1 2
2 6 5
2 5 4
2 9 6
2 3 2
2 7 3
2 1 2
9 10
2 9 3
1 6
2 2 1
2 9 4
1 4
2 8 1
2 8 6
1 5
1 7
2 3 2...

output:

3
4
1
3
3
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

wrong answer 7th numbers differ - expected: '3', found: '-1'

Test #6:

score: 0
Wrong Answer
time: 16ms
memory: 77340kb

input:

1000
10 10
2 1 8
2 8 3
2 3 4
2 2 1
2 4 7
2 7 4
2 9 6
1 5
1 8
2 2 6
2 7 3
2 6 7
2 10 9
2 8 3
2 9 1
2 10 6
2 3 10
2 7 4
2 5 6
2 3 8
9 10
2 8 4
1 3
1 9
2 3 7
2 6 2
2 4 3
2 3 7
2 1 4
2 1 7
2 5 2
2 5 4
2 5 8
2 10 5
2 8 9
2 5 6
1 10
2 8 7
1 10
39 40
2 3 40
2 26 17
2 21 27
2 5 9
1 24
2 19 6
2 25 18
2 18 29...

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:

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

Test #7:

score: 4
Accepted
time: 11ms
memory: 77196kb

input:

1000
10 10
2 2 6
1 2
1 3
1 5
2 9 10
2 6 7
1 7
2 4 8
2 9 4
1 10
2 2 1
2 3 2
2 4 3
2 5 4
2 6 5
2 7 6
2 7 8
2 9 8
2 10 9
2 10 1
9 10
2 1 2
2 2 3
1 7
1 4
2 1 6
2 7 6
2 7 3
2 4 9
2 1 9
2 2 1
2 3 2
2 4 3
2 4 5
2 6 5
2 6 7
2 8 7
2 9 8
2 9 1
9 10
2 1 7
1 10
2 3 6
2 9 5
2 5 4
1 6
2 8 7
2 8 9
2 9 8
2 1 2
2 2 ...

output:

3
4
3
4
2
3
4
3
2
4
3
3
3
5
2
3
5
5
5
3
2
3
3
2
13
4
4
3
1
3
2
2
3
4
4
3
4
2
4
3
4
4
2
3
4
4
3
1
1
3
3
1
4
4
24
4
4
2
4
3
2
2
2
1
3
4
4
2
1
5
4
3
4
0
4
4
4
3
2
4
4
4
4
5
1
3
4
3
3
2
3
2
3
3
4
4
3
1
3
4
3
2
3
3
1
2
35
1
4
3
3
4
4
2
3
3
3
2
4
3
4
3
3
1
3
2
2
17
3
4
2
3
4
11
4
4
3
4
2
9
2
5
2
2
3
3
4
3...

result:

ok 1000 numbers

Test #8:

score: 0
Wrong Answer
time: 19ms
memory: 77928kb

input:

1000
1 10
1 7
1 7
2 10
1 8
1 3
1 8
1 3
2 10
1 1
1 9
1 1
1 9
5 10
1 7
1 6
1 4
1 3
1 10
1 7
1 6
1 4
1 3
1 10
29 40
1 9
1 15
1 29
1 20
1 8
1 30
1 27
1 7
1 24
1 8
1 23
1 17
1 10
1 28
1 26
1 19
1 15
1 33
1 16
1 14
1 10
1 30
1 20
1 40
1 22
1 10
1 31
1 38
1 5
2 28 9
2 15 6
2 39 29
2 20 31
2 8 38
2 30 25
1 ...

output:

1
2
2
5
8
3
3
4
5
1
7
3
5
2
1
2
3
2
4
1
2
14
4
2
3
4
1
3
4
3
3
4
3
4
3
4
4
4
11
10
3
3
3
2
3
4
5
3
2
3
3
3
5
3
10
4
4
2
7
12
3
3
3
3
1
4
2
2
5
4
4
3
3
6
4
2
5
4
3
4
5
3
4
4
3
32
3
2
4
3
4
7
2
4
6
4
3
3
3
4
3
1
3
4
2
4
3
5
4
3
4
3
3
4
2
2
2
5
2
4
3
3
3
2
2
3
3
4
3
1
4
5
3
4
2
3
2
3
4
2
4
13
3
4
3
3
3...

result:

wrong answer 156th numbers differ - expected: '3', found: '-1'

Test #9:

score: 0
Memory Limit Exceeded

input:

1000
5 10
1 7
2 9 8
2 1 4
1 3
2 2 9
1 7
2 9 8
2 1 4
1 3
2 2 9
6 10
2 3 6
2 2 5
2 6 3
2 2 5
2 8 9
1 4
2 6 3
2 5 2
2 6 3
2 5 2
2 9 8
1 4
8 10
1 8
2 5 6
2 5 6
2 3 8
2 9 7
2 7 9
1 4
1 10
1 8
2 6 5
2 6 5
2 8 3
2 7 9
2 7 9
1 4
1 10
6 10
1 9
1 4
1 3
2 7 1
1 5
2 1 6
1 9
1 4
1 3
2 7 1
1 5
2 1 6
6 10
2 6 1
2 ...

output:

result:

Test #10:

score: 0
Wrong Answer
time: 12ms
memory: 77748kb

input:

1000
7 10
2 6 9
2 7 1
2 3 2
2 3 10
2 4 10
1 8
2 2 6
1 9
1 7
2 2 3
1 10
2 2 4
1 8
1 6
6 10
2 2 7
2 10 4
1 9
1 10
2 10 6
1 5
1 7
1 4
1 9
1 10
1 6
1 5
6 10
1 4
2 9 2
2 6 5
1 7
2 6 7
1 10
1 4
1 9
1 5
1 7
1 6
1 10
6 10
2 2 8
1 7
2 3 6
2 6 4
2 10 4
1 8
2 4 2
1 7
2 2 3
1 6
1 10
1 8
6 10
1 5
2 1 2
1 7
2 2 6...

output:

6
6
6
4
5
6
5
5
6
4
4
5
4
19
4
5
3
5
5
5
6
19
5
6
3
6
3
5
4
4
4
4
6
5
34
3
4
5
4
7
6
7
4
3
6
4
6
4
5
4
5
4
7
4
5
6
5
4
4
4
5
6
5
14
5
5
6
5
4
5
7
5
3
5
14
6
5
15
6
5
4
5
5
5
5
4
3
3
4
6
4
5
6
4
6
13
4
4
6
3
5
4
4
4
5
3
4
3
4
3
15
4
5
4
4
5
3
3
5
5
5
4
7
6
5
5
4
7
5
5
5
6
5
3
4
71
6
4
3
6
5
5
6
5
5
3...

result:

wrong answer 22nd numbers differ - expected: '20', found: '19'

Test #11:

score: 0
Wrong Answer
time: 7ms
memory: 77952kb

input:

1000
5 10
1 1
2 6 5
1 5
2 9 7
1 8
2 1 2
1 6
2 1 3
1 7
1 8
7 10
1 8
2 4 7
2 8 5
1 10
2 2 9
1 7
1 6
1 8
1 4
1 5
1 10
1 9
1 7
1 6
5 10
2 2 5
2 4 9
2 9 8
2 9 10
1 6
1 5
1 4
1 8
1 9
1 6
6 10
2 2 5
2 10 7
1 4
2 6 4
1 8
2 5 7
1 5
1 10
1 4
1 6
1 8
1 7
5 10
2 7 8
2 3 1
1 6
1 1
1 8
1 7
2 1 3
1 6
2 1 2
1 8
5 1...

output:

3
7
5
6
3
4
6
5
5
5
7
4
5
35
6
3
5
6
5
4
3
4
5
6
7
4
5
5
4
4
5
4
5
5
7
3
3
6
4
4
6
9
6
4
4
5
6
4
5
6
4
6
5
4
3
4
13
5
4
5
4
5
4
6
5
4
3
5
5
3
5
5
5
5
7
5
6
4
5
5
13
5
5
9
5
5
3
4
4
4
5
7
5
5
3
6
5
4
4
4
5
5
7
-1
-1
-1
-1
-1
-1
-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:

wrong answer 14th numbers differ - expected: '36', found: '35'

Test #12:

score: 0
Wrong Answer
time: 625ms
memory: 83688kb

input:

1000
89 100
2 7 10
2 44 79
2 90 72
2 81 82
2 97 98
1 26
2 12 11
2 19 22
2 75 76
2 87 57
2 93 20
2 14 15
1 18
2 52 56
2 63 65
1 52
2 19 69
2 17 30
1 80
2 87 88
2 32 79
2 65 57
2 10 99
2 74 71
1 90
2 61 62
2 61 40
2 15 59
2 78 53
1 71
2 82 36
2 29 8
2 17 18
2 92 67
2 81 63
2 4 5
2 51 54
2 14 13
1 62
2...

output:

37
38
38
39
35
36
35
32
34
37
33
169
31
34
38
39
41
32
42
34
32
32
26
37
32
43
38
29
164
142
32
38
34
34
40
154
40
36
41
36
31
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-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:

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

Test #13:

score: 0
Wrong Answer
time: 496ms
memory: 82088kb

input:

1000
94 100
2 52 4
1 59
1 47
1 59
2 42 94
2 12 13
2 71 87
2 60 59
2 57 47
2 94 70
1 64
2 12 27
2 77 94
2 50 35
1 5
2 70 58
2 64 56
2 67 68
2 21 29
1 26
2 100 73
2 92 93
1 73
2 71 72
2 38 36
2 50 20
1 74
2 47 87
1 4
1 76
2 92 99
2 82 64
2 48 49
2 15 14
2 38 69
1 51
2 55 42
1 68
1 45
2 21 16
1 30
2 91...

output:

41
27
39
32
35
25
29
33
32
36
40
32
43
45
37
37
43
32
37
158
31
40
431
37
37
43
31
38
30
44
36
45
44
40
170
35
35
35
35
36
30
38
34
41
38
32
440
40
44
34
35
36
34
33
29
37
33
32
42
34
34
30
32
36
34
34
38
418
42
30
33
30
32
32
38
34
38
33
35
28
36
33
32
162
30
36
35
34
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

wrong answer 4th numbers differ - expected: '33', found: '32'

Test #14:

score: 0
Wrong Answer
time: 1616ms
memory: 114100kb

input:

1000
88 90
2 59 42
1 45
2 68 83
2 36 2
2 89 70
1 7
1 8
2 67 55
2 81 47
2 76 36
1 68
2 86 27
1 8
1 12
1 4
2 64 21
2 11 1
2 6 69
2 39 58
2 39 40
1 3
2 39 76
1 62
2 43 69
1 53
1 79
2 78 65
2 85 1
1 75
2 47 87
2 26 41
2 17 38
1 2
2 25 41
2 86 71
1 37
2 31 80
1 14
2 47 12
2 66 78
2 28 83
1 57
1 69
2 53 6...

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:

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

Test #15:

score: 4
Accepted
time: 130ms
memory: 122940kb

input:

1000
86 90
1 2
2 2 79
2 4 89
2 55 4
2 12 6
2 6 70
2 7 9
2 8 39
2 30 10
2 10 35
2 70 8
2 12 13
1 13
2 14 35
2 15 21
2 42 16
1 28
1 18
1 19
2 75 20
2 21 5
2 81 22
2 55 23
2 24 19
1 25
1 62
1 27
1 28
2 59 29
2 31 30
2 32 31
1 32
1 33
1 35
1 35
2 36 70
2 85 29
2 39 38
1 39
1 40
2 18 41
1 42
2 84 44
2 44...

output:

22
25
37
40
30
30
36
26
23
36
29
29
17
27
33
22
37
20
36
26
35
29
40
26
21
40
26
19
33
27
24
37
20
21
29
23
23
22
36
36
34
27
22
39
38
40
39
20
22
18
35
27
36
25
32
21
40
36
21
36
25
19
27
38
37
27
17
25
39
23
25
38
26
26
31
37
27
37
36
17
23
21
23
28
37
27
20
38
29
22
21
20
23
41
22
38
24
22
26
26
...

result:

ok 1000 numbers

Test #16:

score: 4
Accepted
time: 106ms
memory: 120268kb

input:

1000
90 90
2 25 2
2 27 3
2 85 4
2 5 4
2 19 6
2 6 7
2 50 7
2 9 69
1 10
1 11
1 11
1 13
2 14 16
1 15
1 16
2 88 16
1 26
2 76 19
2 19 20
1 20
1 22
2 53 22
2 26 24
1 25
2 25 26
2 8 61
1 23
2 66 29
2 21 30
1 31
2 32 1
2 67 32
2 56 34
1 34
2 36 35
1 36
2 37 40
2 20 39
1 40
2 65 41
2 64 42
2 74 54
2 24 44
2 ...

output:

21
37
29
38
19
27
36
38
23
21
23
38
37
24
19
23
32
27
37
39
18
25
30
28
25
28
24
29
21
32
18
26
34
27
39
29
31
21
21
29
22
31
37
19
27
25
20
36
27
22
37
26
30
24
37
27
35
36
41
27
39
40
16
19
26
24
21
21
37
36
256
36
37
21
37
15
24
24
23
19
39
29
27
38
26
28
38
26
26
40
38
38
19
27
28
38
21
28
20
38...

result:

ok 1000 numbers

Test #17:

score: 0
Wrong Answer
time: 745ms
memory: 119232kb

input:

1000
76 90
1 3
1 83
1 67
1 28
1 17
1 63
1 16
1 13
1 27
1 75
1 12
1 85
1 19
1 40
1 30
1 32
1 58
1 20
1 83
1 72
1 50
1 11
1 53
1 39
1 3
1 58
1 71
1 31
1 6
1 35
1 20
1 62
1 43
1 63
1 32
1 51
1 55
1 73
1 33
1 8
1 34
1 21
1 55
1 44
1 50
1 81
1 84
1 88
1 65
1 53
1 28
1 40
1 14
1 77
1 4
1 87
1 13
1 89
1 11...

output:

28
25
29
36
29
35
31
38
38
31
24
24
25
36
30
36
28
32
31
27
22
31
24
23
29
31
32
29
28
26
32
24
33
31
27
400
25
29
28
30
30
28
29
36
37
28
26
33
31
31
33
32
25
30
34
30
27
26
22
27
39
26
32
37
32
25
22
28
29
26
25
41
34
36
27
31
29
26
29
31
33
29
33
31
27
31
27
36
32
34
29
30
35
30
25
38
33
32
36
27...

result:

wrong answer 289th numbers differ - expected: '35', found: '-1'

Test #18:

score: 0
Wrong Answer
time: 1323ms
memory: 116176kb

input:

1000
83 90
1 34
1 30
1 86
1 13
1 82
1 25
1 83
1 45
1 26
1 12
1 49
1 56
1 73
1 40
1 35
1 34
1 5
1 80
1 69
1 81
1 25
1 67
1 20
1 54
1 62
1 83
1 21
1 35
1 52
1 67
1 47
1 69
1 11
1 85
1 31
1 33
1 51
1 4
1 9
1 63
1 18
1 41
1 63
1 11
1 48
1 43
1 65
1 53
1 61
1 2
1 5
1 76
1 75
1 77
1 64
1 78
1 14
1 72
1 8
...

output:

32
28
29
29
23
38
26
32
31
37
28
31
32
32
27
29
28
29
23
30
36
34
30
26
25
27
25
27
27
32
35
25
24
24
27
25
35
32
28
24
33
31
31
36
31
40
29
27
33
26
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-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:

wrong answer 52nd numbers differ - expected: '33', found: '-1'

Test #19:

score: 0
Wrong Answer
time: 896ms
memory: 103432kb

input:

1000
62 90
1 59
2 46 10
2 85 2
2 79 41
2 34 88
2 49 7
2 66 19
2 77 75
2 26 86
2 68 13
2 71 85
2 11 29
2 65 74
2 80 19
2 87 48
2 17 27
2 21 46
1 44
2 30 27
1 20
2 86 58
2 85 40
2 40 36
2 1 27
2 74 44
1 72
2 14 12
2 18 29
2 39 33
2 66 19
2 90 60
2 47 62
2 52 90
2 12 80
2 68 75
2 51 29
2 1 57
1 61
2 43...

output:

48
50
50
41
42
39
45
48
44
45
48
49
38
50
43
48
46
39
47
46
41
47
45
47
43
40
36
45
50
46
38
52
47
47
44
45
41
36
48
42
39
44
47
44
49
48
42
48
50
46
48
42
46
42
41
44
41
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-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:

wrong answer 59th numbers differ - expected: '42', found: '-1'

Test #20:

score: 0
Wrong Answer
time: 881ms
memory: 105728kb

input:

1000
65 90
2 33 90
2 61 28
2 39 71
2 58 78
2 9 41
2 70 84
2 20 64
2 26 3
2 73 57
2 21 4
2 89 88
2 69 85
2 82 55
2 20 39
2 5 27
2 9 42
2 64 25
2 85 81
2 26 3
1 15
2 87 60
2 86 1
2 10 22
2 66 28
2 66 12
2 19 14
2 8 33
2 84 70
2 11 39
1 16
2 75 37
2 47 39
1 51
2 78 57
2 19 18
2 77 74
2 59 15
2 76 65
2 ...

output:

48
39
44
43
44
43
54
43
45
48
53
50
46
41
46
43
43
46
50
44
47
38
48
42
38
49
40
47
41
50
535
44
47
42
45
50
47
51
42
44
39
49
47
53
48
43
49
43
46
43
51
41
47
49
39
43
46
50
39
43
51
544
53
46
50
44
40
42
37
49
-1
-1
-1
-1
-1
-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:

wrong answer 72nd numbers differ - expected: '48', found: '-1'

Test #21:

score: 0
Wrong Answer
time: 1127ms
memory: 117060kb

input:

1000
76 90
2 15 3
2 61 68
2 35 15
2 67 86
1 36
1 40
2 13 12
2 30 37
2 14 64
2 29 68
2 15 14
2 17 25
2 11 12
2 79 13
2 62 7
2 35 1
2 42 71
2 33 38
1 85
2 47 17
2 39 37
2 60 6
1 77
1 57
2 39 29
1 71
2 30 47
2 30 33
2 64 79
2 42 77
2 45 38
2 33 1
2 75 76
2 18 26
1 18
2 57 56
2 19 55
2 7 81
2 53 19
2 56...

output:

34
33
39
29
38
32
31
35
28
29
35
27
35
31
37
32
31
31
34
29
39
24
29
29
39
36
33
38
34
37
31
34
29
25
33
28
31
32
31
31
32
31
27
28
29
37
35
34
36
32
64804
39
32
32
24
29
29
24
28
38
23
28
33
30
27
29
-1
-1
-1
-1
-1
-1
-1
-1
-1
-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:

wrong answer 4th numbers differ - expected: '30', found: '29'

Test #22:

score: 0
Wrong Answer
time: 455ms
memory: 114184kb

input:

1000
80 90
2 48 50
2 20 23
2 82 8
1 4
1 40
2 69 59
2 13 67
2 6 86
2 3 74
2 9 38
1 9
1 79
1 18
2 15 14
1 31
2 77 21
2 33 72
2 56 39
2 32 33
2 90 89
2 86 83
2 90 13
2 34 26
2 23 68
1 50
2 65 83
1 77
2 79 69
2 25 26
2 44 43
2 74 84
2 13 12
1 62
1 71
2 26 70
2 2 83
2 7 20
2 23 1
2 11 12
2 78 7
1 58
1 65...

output:

32
35
29
41
26
25
31
27
26
29
33
37
31
29
26
32
35
33
37
29
25
35
30
33
33
37
28
36
28
31
32
28
26
34
28
28
34
31
27
28
34
26
37
34
33
29
35
38
35
27
38
27
33
31
33
35
24
22
26
26
27
31
34
31
32
25
35
31
34
28
30
33
30
31
36
28
25
33
42
32
32
33
39
27
31
24
31
28
29
36
28
34
28
32
29
34
35
32
31
31
...

result:

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

Test #23:

score: 0
Wrong Answer
time: 2454ms
memory: 316228kb

input:

1000
82 90
2 36 58
2 64 41
2 1 12
2 6 90
2 50 15
2 30 27
2 42 87
2 89 33
2 47 28
1 70
1 17
1 20
2 33 62
2 31 7
2 4 69
2 83 37
2 55 36
2 35 32
2 29 11
1 57
2 53 52
2 9 53
2 88 66
1 21
1 22
2 28 39
2 11 12
1 5
2 78 56
2 59 57
2 63 8
2 85 62
2 84 16
2 48 49
2 7 61
2 3 9
1 4
1 50
1 80
2 62 43
2 77 50
2 ...

output:

32
34
34
33
29
36
31
38
38
33
23
33
28
37
32
41
35
35
34
25
34
29
30
24
27
38
36
40
30
29
35
30
38
28
36
31
29
35
38
34
29
29
27
25
31
30
47
30
30
42
37
33
25
35
27
29
38
38
33
27
31
34
28
39
35
35
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-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:

wrong answer 4th numbers differ - expected: '34', found: '33'

Test #24:

score: 0
Wrong Answer
time: 2922ms
memory: 309756kb

input:

1000
83 90
2 71 72
2 6 16
2 78 3
2 24 25
2 39 65
2 19 9
2 10 14
1 30
2 86 65
2 17 18
1 47
2 69 68
1 7
2 64 7
2 31 68
2 90 89
2 85 4
2 22 79
2 12 62
2 56 66
1 83
1 88
2 43 45
2 50 20
2 15 14
2 38 59
1 32
1 80
2 33 6
1 61
2 15 41
2 47 20
2 78 52
2 1 13
1 18
2 6 63
2 70 62
2 25 27
1 74
2 8 2
2 65 41
2 ...

output:

36
29
31
31
34
32
33
35
32
30
30
26
31
36
33
26
29
27
35
32
26
37
30
32
27
29
26
32
32
36
37
24
34
33
29
29
36
41
34
34
25
34
32
24
21
36
32
32
32
30
34
32
36
33
29
29
38
29
27
33
30
32
29
31
32
35
37
31
29
24
26
32
33
28
30
29
35
38
31
25
34
32
29
37
34
29
28
34
32
32
29
33
31
27
34
34
28
34
25
31
...

result:

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

Test #25:

score: 0
Wrong Answer
time: 2322ms
memory: 316028kb

input:

1000
80 90
2 66 52
2 74 17
2 42 71
2 59 58
2 86 21
1 81
2 25 63
1 52
1 1
1 25
2 2 22
1 89
1 39
1 28
2 78 85
2 67 76
1 85
2 30 31
2 12 13
2 25 38
1 33
2 38 71
1 9
2 62 61
1 16
1 54
2 52 66
2 5 15
2 14 13
2 69 3
2 70 66
2 37 25
2 21 27
2 34 6
2 44 85
2 12 33
1 75
2 51 53
2 4 45
2 39 82
1 26
1 15
2 46 ...

output:

38
30
31
25
32
396
36
33
34
31
32
37
36
32
32
37
26
37
30
38
30
34
39
29
36
31
28
30
40
38
28
31
41
33
36
30
35
35
30
33
33
39
38
29
30
29
30
30
31
34
34
37
33
38
33
39
34
39
30
35
28
33
30
33
37
40
38
33
30
34
37
33
31
40
37
30
34
35
32
36
34
37
37
37
33
25
38
37
29
28
39
29
37
30
33
32
29
37
30
35...

result:

wrong answer 2nd numbers differ - expected: '31', found: '30'
English 繁體中文 简体中文

Server Time: 2024-12-03 00:40:58 | OpenSource Project