QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#509274#6315. 填数游戏TheRaptor12 2717ms316980kbC++145.2kb2024-08-08 13:11:452024-08-08 13:11:46

Judging History

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

  • [2024-08-08 13:11:46]
  • 评测
  • 测评结果：12
  • 用时：2717ms
  • 内存：316980kb
查看
  • [2024-08-08 13:11:45]
  • 提交

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]){
		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.first==p) continue;
		chain.push_back({i.second,{x,i.first}});
		if(key[i.first]==0) continue;
		getloop(i.first,x);
		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){
	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];
	}
}
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]=0;
		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]) 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){
				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=1; 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: 11ms
memory: 77504kb

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:

5
0
3
1
1
2
6
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

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

Test #2:

score: 0
Wrong Answer
time: 8ms
memory: 77060kb

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
4
7
8
3
3
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

wrong answer 2nd numbers differ - expected: '5', found: '4'

Test #3:

score: 0
Wrong Answer
time: 11ms
memory: 78160kb

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: 3ms
memory: 77360kb

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:

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

result:

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

Test #5:

score: 0
Wrong Answer
time: 11ms
memory: 77836kb

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:

2
3
3
3
3
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

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

Test #6:

score: 0
Wrong Answer
time: 15ms
memory: 78736kb

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: 16ms
memory: 77624kb

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: 12ms
memory: 77616kb

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:

0
1
1
4
9
2
2
3
4
0
11
2
4
1
0
1
2
2
3
0
1
14
3
2
2
3
1
2
3
2
2
3
2
3
2
3
3
3
11
10
2
2
2
1
2
3
4
2
1
2
3
2
4
2
12
3
3
2
6
12
2
2
2
2
0
3
1
2
4
3
3
2
2
5
3
1
4
3
2
3
5
2
3
3
2
32
2
1
3
2
3
6
1
3
5
4
2
2
2
3
2
1
2
3
1
3
2
4
3
2
3
2
3
3
1
1
1
4
1
3
3
2
2
1
1
2
2
3
2
0
3
4
2
3
1
2
1
2
3
1
3
11
2
3
2
2
...

result:

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

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: 11ms
memory: 78100kb

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:

5
5
5
5
4
5
4
4
5
4
4
4
3
18
3
4
2
4
4
4
5
15
6
5
2
5
2
4
3
4
3
3
5
4
34
2
3
4
3
6
5
6
3
2
5
3
5
3
4
4
4
4
6
3
4
5
4
3
3
3
4
5
4
14
4
5
5
4
3
4
6
4
3
5
14
5
4
14
5
4
3
4
4
4
4
3
2
2
3
5
4
4
5
3
5
13
3
4
5
3
4
3
3
3
4
3
4
3
3
2
15
3
4
3
4
4
2
2
5
4
4
3
6
5
5
4
3
6
4
4
4
5
5
4
3
72
5
3
2
5
4
4
6
4
4
2...

result:

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

Test #11:

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

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
6
4
5
2
3
5
4
4
4
6
3
5
35
5
2
4
5
4
3
3
4
4
5
6
3
4
4
3
3
5
3
4
4
6
3
4
5
3
4
5
9
5
3
3
4
5
3
5
5
3
5
4
4
3
3
15
5
3
4
4
4
3
5
4
3
2
4
4
2
5
4
4
4
6
4
5
3
4
4
11
4
4
10
5
4
2
4
3
3
4
6
4
4
2
5
4
3
3
3
4
4
6
-1
-1
-1
-1
-1
-1
-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: '7', found: '6'

Test #12:

score: 0
Wrong Answer
time: 555ms
memory: 82960kb

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:

38
36
37
41
36
36
33
37
36
35
33
171
30
35
39
39
42
33
41
41
32
32
26
41
32
40
36
28
170
146
30
39
37
36
42
162
41
41
40
34
33
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-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: '39', found: '36'

Test #13:

score: 0
Wrong Answer
time: 504ms
memory: 82444kb

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:

37
30
40
34
37
30
30
38
37
38
40
32
43
48
41
36
47
37
34
172
31
42
473
34
43
40
33
37
34
45
37
44
43
41
173
43
37
40
42
34
31
40
36
38
42
32
456
40
47
38
35
34
35
34
30
35
35
28
39
36
33
31
34
35
35
34
39
451
43
29
36
32
33
35
44
34
41
38
38
29
36
33
31
168
34
34
33
37
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

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

Test #14:

score: 0
Wrong Answer
time: 1726ms
memory: 111756kb

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: 140ms
memory: 127544kb

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: 134ms
memory: 125640kb

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: 815ms
memory: 116048kb

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:

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

result:

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

Test #18:

score: 0
Wrong Answer
time: 1426ms
memory: 119460kb

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:

33
28
29
34
26
39
27
35
30
43
31
31
35
31
30
28
28
30
27
30
41
34
31
29
30
32
27
27
30
34
35
26
27
22
29
31
37
32
29
23
34
31
33
35
32
41
34
28
32
30
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-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: '32', found: '33'

Test #19:

score: 0
Wrong Answer
time: 963ms
memory: 103284kb

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:

49
53
52
42
42
42
47
44
45
46
54
48
44
55
50
46
47
39
50
46
42
47
45
56
44
40
39
47
53
52
41
54
52
48
44
46
41
40
52
46
36
45
53
50
48
54
41
53
48
52
49
47
47
44
46
42
40
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-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: '48', found: '49'

Test #20:

score: 0
Wrong Answer
time: 945ms
memory: 106144kb

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:

46
46
54
43
44
45
58
45
46
51
54
49
50
45
43
45
44
46
48
48
57
39
48
47
37
53
45
48
45
53
605
48
51
42
44
47
50
54
41
46
43
51
49
57
48
52
48
43
44
44
52
41
49
51
41
43
51
54
44
47
53
646
58
49
50
49
39
45
37
47
-1
-1
-1
-1
-1
-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: '48', found: '46'

Test #21:

score: 0
Wrong Answer
time: 1191ms
memory: 116988kb

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
31
36
36
38
35
33
34
29
28
36
25
33
30
39
30
33
30
35
28
37
28
29
30
37
37
33
39
31
34
32
33
32
26
34
29
35
32
36
29
31
31
28
28
33
35
38
36
34
34
72736
40
35
34
24
30
31
25
24
38
25
27
28
34
25
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 2nd numbers differ - expected: '33', found: '31'

Test #22:

score: 0
Wrong Answer
time: 494ms
memory: 119588kb

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:

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

result:

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

Test #23:

score: 0
Wrong Answer
time: 2717ms
memory: 316980kb

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:

31
39
35
37
31
34
42
35
41
34
24
30
32
36
33
37
32
33
33
28
35
26
31
26
24
35
36
39
28
28
33
31
37
27
36
34
28
33
38
35
28
30
28
27
30
30
43
29
34
43
35
30
29
35
25
31
36
34
33
27
34
29
31
39
33
34
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-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: '32', found: '31'

Test #24:

score: 0
Time Limit Exceeded

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:

result:

Test #25:

score: 0
Wrong Answer
time: 2624ms
memory: 315456kb

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:

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

result:

wrong answer 1st numbers differ - expected: '38', found: '39'
English 繁體中文 简体中文

Server Time: 2024-12-02 22:34:57 | OpenSource Project