QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#461720 | #8816. Solar Panel Grid Optimization | Crysfly | TL | 257ms | 23948kb | C++17 | 2.8kb | 2024-07-03 00:06:31 | 2024-07-03 00:06:31 |
Judging History
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
*/
Details
Tip: Click on the bar to expand more detailed information
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...