QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#39751#2931. Tri-Color PuzzleLangdao_ZhangAC ✓3ms4188kbC++3.1kb2022-07-13 11:14:482022-07-13 11:14:49

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-13 11:14:49]
  • Judged
  • Verdict: AC
  • Time: 3ms
  • Memory: 4188kb
Show
  • [2022-07-13 11:14:48]
  • Submitted

answer

#include<iostream>

#define lint int64_t
#define ulint uint64_t

#define maxn 21
#define maxm 602
#define mod 3

using
		namespace
					std;

int n,m;
int id[maxn][maxn];
int val[maxn][maxn];
int x[maxm],y[maxm],c;
int mat[maxm][maxm],r;

void debug_mat(){
	
	for(int i=0;i<r;i++){
		
		for(int j=0;j<c;j++){
			
			printf("%d ",mat[i][j]);
		}
		printf("= %d\n",mat[i][c]);
	}
}

ulint qow(ulint a,ulint b){
	
	ulint ans=1;
	for(;b;a=a*a,b>>=1) if(b&1) ans=ans*a;
	return ans;
}

bool empty_row(int u){
	
	for(int i=0;i<c;i++){
		
		if(mat[u][i]) return false;
	}
	
	return true;
}

void swap_row(int u,int v){
	
	if(u==v) return;
	
	for(int i=0;i<=c;i++){
		
		swap(mat[u][i],mat[v][i]);
	}
}

void GE(){
	
//	for(int i=1;i<=n;i++){
//		
//		for(int j=1;j<=i;j++){
//			
//			cout<<val[i][j]<<' ';
//		}
//		cout<<endl;
//	}
	
	for(int i=2;i<=n;i++){
		
		for(int j=1;j<i;j++){
			
			bool valid=false;
			
			if(~id[i][j]) mat[r][id[i][j]]=1,valid|=true;
			if(~id[i-1][j]) mat[r][id[i-1][j]]=1,valid|=true;
			if(~id[i][j+1]) mat[r][id[i][j+1]]=1,valid|=true;
			mat[r][c]=(3*mod-val[i][j]-val[i-1][j]-val[i][j+1])%mod;
			
			if(!valid&&mat[r][c]){
				
				printf("0\n");
				return;
			}
			
			//cout<<"||"<<i<<' '<<j<<' '<<valid<<endl;
			
			if(!valid){
				
				continue;
			}
			
			r++;
		}
	}
	
//	for(int i=2;i<n;i++){
//		
//		for(int j=1;j<i;j++){
//			
//			bool valid=false;
//			
//			if(~id[i][j]) mat[r][id[i][j]]=1,valid|=true;
//			if(~id[i][j+1]) mat[r][id[i][j+1]]=1,valid|=true;
//			if(~id[i+1][j+1]) mat[r][id[i+1][j+1]]=1,valid|=true;
//			mat[r][c]=(3*mod-val[i][j]-val[i][j+1]-val[i+1][j+1])%mod;
//			
//			if(!valid&&mat[r][c]){
//				
//				printf("0\n");
//				return;
//			}
//			
//			//cout<<"||"<<i<<' '<<j<<' '<<valid<<endl;
//			
//			if(!valid){
//				
//				continue;
//			}
//			
//			r++;
//		}
//	}
	
	//debug_mat();
	//printf("\n");
	
	int i=0,p=0;
	
	for(;i<r&&p<c;i++,p++){
		
		int nxti=i;
		
		while(nxti<r&&!mat[nxti][p]){
			
			nxti++;
		}
		
		if(nxti==r){
			
			i--;
			continue;
		}
		
		swap_row(i,nxti);
		
		for(int j=i+1;j<r;j++){
			
			int f=mat[i][p]*mat[j][p]%mod;
			
			for(int k=0;k<=c;k++){
				
				mat[j][k]=(mat[j][k]+f*(mod-mat[i][k]))%mod;
			}
		}
	}
	
	//debug_mat();
	
	for(int i=r-1;~i;i--){
		
		if(empty_row(i)){
			
			if(mat[i][c]){
				
				printf("0\n");
				return;
			}
		}
	}
	
	printf("%llu\n",qow(3,c-i));
}

signed main(){
	
	scanf("%d %d",&n,&m);
	
	for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) val[i][j]=-1;
	for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) id[i][j]=-1;
	
	int u,v,w;
	
	for(int i=0;i<m;i++){
		
		scanf("%d %d %d",&u,&v,&w);
		
		val[u][v]=w;
	}
	
	for(int i=1;i<=n;i++){
		
		for(int j=1;j<=n;j++){
			
			if(val[i][j]<0){
				
				x[c]=i;
				y[c]=j;
				id[i][j]=c;
				c++;
				
				val[i][j]=0;
			}
		}
	}
	
	GE();
	
end:
	return EOF+1;
}
/*
4 4
1 1 0
2 1 2
4 1 2
4 4 2

4 4
1 1 1
2 1 2
4 1 2
3 3 2

4 4
1 1 0
2 1 1
4 1 0
4 4 0
*/
源文件, 语言: C++

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3628kb

input:

4 4
1 1 0
2 1 2
4 1 2
4 4 2

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3748kb

input:

4 4
1 1 1
2 1 2
4 1 2
3 3 2

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

4 4
1 1 0
2 1 1
4 1 0
4 4 0

output:

3

result:

ok single line: '3'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

6 4
1 1 0
2 2 0
5 1 1
5 5 2

output:

9

result:

ok single line: '9'

Test #5:

score: 0
Accepted
time: 1ms
memory: 4060kb

input:

17 16
3 2 2
4 4 0
5 2 1
6 4 1
8 5 2
8 8 2
11 1 2
11 7 0
12 4 2
12 10 2
12 11 0
13 11 2
14 5 2
14 8 0
16 7 0
17 5 1

output:

3

result:

ok single line: '3'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

11 9
2 2 2
5 3 0
6 5 2
9 7 1
10 10 1
11 4 1
11 7 0
11 10 1
11 11 2

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

4 4
2 1 1
4 1 2
4 3 1
4 4 2

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 3ms
memory: 4004kb

input:

16 7
6 3 0
9 5 0
11 11 2
12 7 1
13 10 2
14 7 0
15 10 1

output:

19683

result:

ok single line: '19683'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3728kb

input:

10 4
4 3 2
8 2 2
8 6 1
9 5 0

output:

729

result:

ok single line: '729'

Test #10:

score: 0
Accepted
time: 1ms
memory: 4128kb

input:

18 29
4 1 2
6 5 0
7 3 2
7 5 0
8 6 1
9 1 0
9 6 1
10 1 0
10 2 0
10 3 0
10 6 1
11 2 2
11 8 2
11 11 0
13 8 0
14 3 1
14 5 1
14 6 1
14 9 0
14 12 0
15 4 1
15 7 1
15 11 1
15 14 2
16 8 1
16 9 0
16 15 2
18 6 1
18 16 2

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3784kb

input:

5 5
3 2 0
3 3 1
4 1 1
5 1 0
5 3 0

output:

1

result:

ok single line: '1'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

11 8
4 3 0
6 3 1
6 5 0
6 6 1
7 3 2
10 3 0
10 7 0
11 11 2

output:

27

result:

ok single line: '27'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3732kb

input:

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

output:

1

result:

ok single line: '1'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3784kb

input:

11 7
3 2 0
3 3 2
5 1 0
7 3 2
10 1 1
10 6 2
10 8 0

output:

81

result:

ok single line: '81'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3752kb

input:

8 7
3 1 2
4 2 1
5 2 0
5 3 1
5 4 0
6 3 2
8 8 2

output:

0

result:

ok single line: '0'

Test #16:

score: 0
Accepted
time: 3ms
memory: 4188kb

input:

19 5
9 7 0
11 10 0
18 9 0
19 10 1
19 17 0

output:

4782969

result:

ok single line: '4782969'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3748kb

input:

11 9
7 3 1
7 5 0
7 6 2
8 4 0
8 7 2
9 3 0
10 3 0
10 9 0
11 1 2

output:

0

result:

ok single line: '0'
English 繁體中文 简体中文

伺服器時間: 2025-04-08 18:10:52 | 開源專案