QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#461720#8816. Solar Panel Grid OptimizationCrysflyTL 257ms23948kbC++172.8kb2024-07-03 00:06:312024-07-03 00:06:31

Judging History

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

  • [2024-07-03 00:06:31]
  • 评测
  • 测评结果:TL
  • 用时:257ms
  • 内存:23948kb
  • [2024-07-03 00:06:31]
  • 提交

answer

// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#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
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
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 1000005
#define inf 0x3f3f3f3f

int n,a[25][25],b[25][25],st[25],go[25][25];
int f[1<<20|5]; pii pf[1<<20|5];
int g[1<<20|5]; pii pg[1<<20|5];

vector<pii>out;
void row(int i){
	out.pb(mkp(i,0));
	int p=a[i][0];
	For(j,0,n-2) a[i][j]=a[i][j+1];
	a[i][n-1]=p;
}
void col(int i){
	out.pb(mkp(i,1));
	int p=a[n-1][i];
	Rep(j,n-1,1) a[j][i]=a[j-1][i];
	a[0][i]=!p;
}

int rd(){
	char ch;
	while(!isdigit(ch=getchar()));
	return ch&1;
}
void print(){
	For(i,0,n-1){
		For(j,0,n-1)cout<<a[i][j];
		cout<<"\n";
	}
}
signed main()
{
	n=read();
	For(i,0,n-1)For(j,0,n-1)a[i][j]=rd();
	For(i,0,n-1)For(j,0,n-1)b[i][j]=rd();
	int xo=0;
	For(i,0,(1<<n)-1) f[i]=inf;
	For(i,0,n-1){
		int s=0;
		For(j,0,n-1)if(a[j][i]!=b[j][i])s^=(1<<j);
		xo^=s;
		st[i]=s;
	}
	f[xo]=0;
//	cout<<"xor "<<xo<<"\n";
	
	For(i,0,n-1){
		int ta=0,tb=0;
		For(j,0,n-1) ta|=(a[j][i]<<j),tb|=(b[j][i]<<j);
		memcpy(g,f,sizeof g);
		For(j,1,2*n-1){
			int o=(ta>>(n-1)&1);
			ta<<=1,ta^=(o<<n),ta^=(!o);
			
			int t=st[i]^ta^tb;
			go[i][j]=t;
			For(s,0,(1<<n)-1)
				if(f[s]+j<g[s^t]) g[s^t]=f[s],pg[s^t]=mkp(i,j);
		}
		For(s,0,(1<<n)-1)
			if(g[s]<f[s]) f[s]=g[s],pf[s]=pg[s];
	}
	
	int now=0;
	if((n-1)%2) now=(1<<n)-1;
	int mn=f[now];
	if(mn==inf) exit(233);
	
	while(now!=xo){
		pii p=pf[now];
		int i=p.fi,j=p.se;
		now^=go[i][j];
	//	cout<<"turn "<<i<<" "<<j<<"\n";
		For(_,1,j) col(i);
	}
	
//	For(i,0,n-1){
//		For(j,0,n-1)cout<<b[i][j]<<" \n"[j==n-1];
//	}
	
	For(j,0,n-2){
		vi o;
	//	For(i,0,n-1) cout<<b[i][j]; cout<<" b\n";
		
	//	print(); puts("-a-");
		For(i,0,n-1)
			if(b[i][j]==a[i][n-1]) row(i);//cout<<"R "<<i<<"\n";
			else o.pb(i);
	//	print(); puts("--");
		For(_,1,n) col(n-1);
		for(int i:o) row(i);
		
	//	print(); puts("-----");
	}
	
	
	cout<<out.size()<<"\n";
	for(auto [x,y]:out) cout<<(y?"column":"row")<<" "<<x+1<<"\n";
	return 0;
}
/*

3
000
110
010

101
110
011

3
000
110
010

101
110
011
4
1011
1100
0100
1011

1001
0110
0110
1001
*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 12000kb

input:

4
1011
1100
0100
1011

1001
0110
0110
1001

output:

29
column 1
column 1
column 1
column 1
column 1
row 1
row 2
row 3
row 4
column 4
column 4
column 4
column 4
row 1
row 2
row 3
row 4
column 4
column 4
column 4
column 4
column 4
column 4
column 4
column 4
row 1
row 2
row 3
row 4

result:

ok Accepted! 29 steps.

Test #2:

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

input:

3
110
111
101

111
010
111

output:

14
column 2
column 1
row 3
column 3
column 3
column 3
row 1
row 2
row 2
column 3
column 3
column 3
row 1
row 3

result:

ok Accepted! 14 steps.

Test #3:

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

input:

4
1101
1000
0011
1010

0110
0011
1010
1010

output:

32
column 2
column 1
column 1
column 1
column 1
column 1
column 1
column 1
row 2
row 3
column 4
column 4
column 4
column 4
row 1
row 4
row 1
row 3
row 4
column 4
column 4
column 4
column 4
row 2
row 2
row 3
row 4
column 4
column 4
column 4
column 4
row 1

result:

ok Accepted! 32 steps.

Test #4:

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

input:

5
10000
00000
00001
00000
01001

00000
00001
01010
00001
00000

output:

46
column 2
column 1
column 1
column 1
column 1
column 1
row 1
row 2
row 4
column 5
column 5
column 5
column 5
column 5
row 3
row 5
row 2
row 3
row 4
column 5
column 5
column 5
column 5
column 5
row 1
row 5
row 1
row 5
column 5
column 5
column 5
column 5
column 5
row 2
row 3
row 4
row 2
row 4
column...

result:

ok Accepted! 46 steps.

Test #5:

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

input:

6
111111
111111
111111
111111
111111
111111

111111
111111
111111
111111
111111
111111

output:

66
column 1
column 1
column 1
column 1
column 1
column 1
row 1
row 2
row 3
row 4
row 5
row 6
column 6
column 6
column 6
column 6
column 6
column 6
row 1
row 2
row 3
row 4
row 5
row 6
column 6
column 6
column 6
column 6
column 6
column 6
column 6
column 6
column 6
column 6
column 6
column 6
row 1
row...

result:

ok Accepted! 66 steps.

Test #6:

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

input:

7
1000000
1101010
1110010
0101000
1110011
0001100
1000010

1100100
1000010
0001000
1001101
1010110
0000001
1010111

output:

96
column 2
column 2
column 2
column 2
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
row 3
row 5
row 6
column 7
column 7
column 7
column 7
column 7
column 7
column 7
row 1
row 2
row 4
row 7
row 1
row 2
row 4
row 5
column 7
column 7
column 7
column 7
column 7
column 7
column...

result:

ok Accepted! 96 steps.

Test #7:

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

input:

8
10000000
01100110
11000110
01010000
10000101
01101100
01001111
00110101

00011110
00000001
00111000
01011101
01000111
01010001
01101001
11010000

output:

112
row 1
row 2
row 3
row 4
row 6
row 8
column 8
column 8
column 8
column 8
column 8
column 8
column 8
column 8
row 5
row 7
row 1
row 3
row 4
row 5
row 6
row 8
column 8
column 8
column 8
column 8
column 8
column 8
column 8
column 8
row 2
row 7
row 4
row 6
row 7
column 8
column 8
column 8
column 8
co...

result:

ok Accepted! 112 steps.

Test #8:

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

input:

9
000000000
010000000
000000000
100000010
010001000
000000000
000100000
100000010
000001001

110000000
000110001
100000100
000100000
000000100
000010000
000000000
000000000
000000000

output:

160
column 3
column 3
column 3
column 2
column 2
column 2
column 2
column 2
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
row 2
row 4
row 5
row 6
row 7
row 8
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
row 1
row 3
row 9
row 1
row 2
row 3...

result:

ok Accepted! 160 steps.

Test #9:

score: 0
Accepted
time: 5ms
memory: 11680kb

input:

10
0001011101
1101000101
1111101111
0110001110
1111011111
0011101110
1101100001
1000001111
1011011111
1111100110

1101101000
1111001011
1101011100
1000111110
0101001000
0011111101
1111011111
1100100111
1110101111
1110110101

output:

202
column 4
column 3
column 3
column 2
column 2
column 2
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
row 1
row 2
row 3
row 6
row 7
row 8
row 9
column 10
column 10
column 10
column 10
column 10
column...

result:

ok Accepted! 202 steps.

Test #10:

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

input:

11
01101011000
00000000010
01001110100
00000000100
10010001110
11000000101
10000010000
10001010011
00100000100
10100000000
11000000100

00101110001
01100001100
10010000000
00011111000
01001000000
00100000001
11000000000
10000101001
00001000000
01010100011
11001000000

output:

244
column 3
column 3
column 3
column 3
column 3
column 2
column 2
column 2
column 2
column 2
column 2
column 2
column 2
column 2
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
row 1
row 2
row 4
row 5
row 8
row 9
row 10
column 11
column 11
column 11
column ...

result:

ok Accepted! 244 steps.

Test #11:

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

input:

12
000000000000
000000000100
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000

000100000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
0000000000...

output:

278
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
row 1
row 2
row 3
row 4
row 5
row 6
row 7
row 8
row 9
row 10
row 11
row 12
column 12
column 12
column 12
column 12
column 12
column 12
column 12
column 12
column 12
colum...

result:

ok Accepted! 278 steps.

Test #12:

score: 0
Accepted
time: 7ms
memory: 11792kb

input:

13
0111111010110
0101111010110
1111110111111
0100110111110
1100111011011
1111100110110
0111011101111
0110111011111
1110111101101
0111111011101
0101000011101
1110111100110
0010100011111

1101011011111
0111111111111
0010010111101
0111011110000
1000101011111
1100101101001
0111111111110
1110110111100
11...

output:

348
column 4
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 2
column 2
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1...

result:

ok Accepted! 348 steps.

Test #13:

score: 0
Accepted
time: 4ms
memory: 11884kb

input:

14
00100000110000
10000000001000
10000000110000
00001000000000
00100000000001
00100000000001
00000000010000
00000000010000
00000001000000
00010010000000
00000000000000
00100000000000
00000000000000
10000000100000

00000000001000
10000000000100
01000000100000
00000000000000
00000110000011
00100000000...

output:

384
column 4
column 4
column 4
column 3
column 2
column 2
column 2
column 2
column 2
column 2
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
row 1
row 3
row 4
row 7
row 8
row 9
row 10
row 11
row 12
row 13
row 14
column 14
column 14
column 14
column 14
colum...

result:

ok Accepted! 384 steps.

Test #14:

score: 0
Accepted
time: 11ms
memory: 12208kb

input:

15
011101111011111
111111111101111
111111111110111
111111111111111
111111111011011
111011111011101
010111111111111
111111101111111
111110110111111
111111110111111
111001110111111
111111111101101
011111110111011
100110101110110
101111011111111

011111111111111
111111011111111
111111101011111
00101111...

output:

464
column 5
column 4
column 4
column 4
column 4
column 4
column 4
column 4
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 2
column 2
column 2
column 2
column 2
column 2
column 2
column 1
column 1
column 1
column 1
column 1...

result:

ok Accepted! 464 steps.

Test #15:

score: 0
Accepted
time: 24ms
memory: 19992kb

input:

16
1111110101010011
1111111111101101
0111111111111111
1101101111101000
1101011101111111
1110011101111011
0111111111110111
1111111101011101
1111111000011111
1101011111101111
1101110100111011
1111111111101110
1011111111011011
1111011010001100
1111111111101001
0110010111110110

1001101110000011
1000111...

output:

524
column 4
column 4
column 4
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 2
column 2
column 2
column 2
column 2
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1...

result:

ok Accepted! 524 steps.

Test #16:

score: 0
Accepted
time: 52ms
memory: 18280kb

input:

17
11010000101111110
11010010010011111
00010100001100110
01110011010101000
01100101110110101
01101001001010011
10101010000111111
01101000001010100
01100100001111010
11110011010110011
10110001001010100
10100111100111000
01001001011011001
01110110111011100
11010111101010101
00100001100110101
010011100...

output:

570
column 5
column 4
column 4
column 4
column 4
column 4
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 3
column 2
column 2
column 2
column 1
column 1
column 1
column 1
column 1
row 3
row 5
row 6
row 7
row 8
row 11
row 13
row 14
row 16
colu...

result:

ok Accepted! 570 steps.

Test #17:

score: 0
Accepted
time: 122ms
memory: 17304kb

input:

18
101011101111111100
101011011110111101
101101001010101011
010011011001100000
011011110110011110
010111111001100001
100101111001100001
101100111100111111
110000101101101110
111111110010100111
011011101100111011
111110101110110011
011101101010011011
010010001111011011
101111110101100111
011000001111...

output:

636
column 3
column 2
column 2
column 2
column 2
column 2
column 2
column 2
column 2
column 2
column 2
column 2
column 2
column 2
column 2
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
row 4
row 6
row 7
row 12
row 13
row 14
row 16
row 18
column 18
column 18
column ...

result:

ok Accepted! 636 steps.

Test #18:

score: 0
Accepted
time: 257ms
memory: 23948kb

input:

19
0110101001111111000
1011110111000000011
1110111111110100101
1111110010111110111
1111110111101111110
0111001101011101101
0111111110101011100
0000010001010101010
1101011001001110011
1110101100101011001
1110100010001101001
1011000010101101001
1011010111011101010
1010010011101000101
01111001110010111...

output:

706
column 5
column 5
column 4
column 4
column 4
column 4
column 4
column 4
column 4
column 4
column 3
column 3
column 3
column 3
column 2
column 2
column 2
column 2
column 2
column 2
column 2
column 2
row 1
row 2
row 3
row 6
row 7
row 8
row 9
row 11
row 14
row 18
column 19
column 19
column 19
colum...

result:

ok Accepted! 706 steps.

Test #19:

score: -100
Time Limit Exceeded

input:

20
11101101111000111000
01101100100001001010
00001010110101000010
10011000000001101010
00100011110101011010
11100001011000011001
01010110010111000000
11100100010000100111
10000100011000111101
11101101001100111001
10000000011011011001
01000100101110000101
00101010001101000000
01010101000000000000
000...

output:


result: