QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #483384 | #9114. Black or White 2 | ucup-team1525# | AC ✓ | 467ms | 32544kb | C++20 | 5.8kb | 2024-07-18 16:33:27 | 2024-07-18 16:33:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int t,n,m,k;
const int N=1505;
int a[N][N];
// int f[12][100][1<<8],fr[10][100][1<<8];
// int n,m,k;
// int calc(int x,int y)
// {
// int sum=0;
// for (int i=0;i<n-1;++i)
// {
// int o=(x>>i)&1,p=(x>>(i+1))&1,q=(y>>i)&1,r=(y>>(i+1))&1;
// if (o+p+q+r==2)
// ++sum;
// }
// return sum;
// }
const int inf=1e9+7;
int f[65][70][1<<9],fr[65][70][1<<9];
int prea[9][9][70][9][9];
void prework(int n,int m,int k,int a[9][9])
{
for (int i=1;i<=n*m;++i)
for (int j=0;j<=k;++j)
for (int l=0;l<(1<<(n+1));++l)
f[i][j][l]=inf;
for (int i=0;i<(1<<n);++i)
if (__builtin_popcount(i)<=k)
f[n][k-__builtin_popcount(i)][i]=0;
int mask=(1<<(n+1))-1;
for (int i=2;i<=m;++i)
{
for (int j=1;j<=n;++j)
{
for (int l=0;l<=k;++l)
for (int o=0;o<(1<<(n+1));++o)
{
int id=(i-1)*n+j;
if (f[id-1][l][o]<inf)
{
int tmp=o&1;
if ((o>>n)&1) ++tmp;
if (((o>>(n-1))&1)) ++tmp;
if (j==1)
tmp=-1;
if (l!=0)
{
if (f[id][l-1][((o<<1)&mask)|1]>f[id-1][l][o]+(tmp==1?1:0))
{
f[id][l-1][((o<<1)&mask)|1]=f[id-1][l][o]+(tmp==1?1:0);
fr[id][l-1][((o<<1)&mask)|1]=o;
}
}
if (f[id][l][((o<<1)&mask)]>f[id-1][l][o]+(tmp==2?1:0))
{
f[id][l][((o<<1)&mask)]=f[id-1][l][o]+(tmp==2?1:0);
fr[id][l][((o<<1)&mask)]=o;
}
}
}
// for (int l=0;l<=k;++l)
// for (int o=0;o<(1<<n);++o)
}
}
int mnp=0;
for (int i=1;i<(1<<(n+1));++i)
if (f[n*m][0][i]<f[n*m][0][mnp])
mnp=i;
int s=0;
for (int i=m;i>=2;--i)
for (int j=n;j>=1;--j)
{
a[j][i]=mnp&1;
mnp=fr[(i-1)*n+j][s][mnp];
s+=a[j][i];
}
for (int i=n;i>=1;--i)
{
a[i][1]=mnp&1;
mnp>>=1;
}
}
void solve()
{
scanf("%d%d%d",&n,&m,&k);
int inv=0,trp=0;
if (k>n*m/2)
{
k=n*m-k;
inv=1;
}
if (n>m)
{
swap(n,m);
trp=1;
}
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
a[i][j]=0;
if (m<=8)
{
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
a[i][j]=prea[n][m][k][i][j];
}
else
{
if (k>=2*n)
{
int p=(k-(n+1)/2)/n+1;
int sum=p*n+(n+1)/2;
if (p==3&&k<3*n)
{
k-=(n+1)/2;
for (int j=1;j<=n;j+=2)
a[j][m]=1;
p=(k-(n+1)/2)/n+1;
sum=p*n+(n+1)/2;
}
for (int i=1;i<=n;++i)
for (int j=1;j<=p;++j)
{
a[i][j]=1;
// if (sum>=k&&i%2==1&&j%2==1)
// {
// --sum;
// a[i][j]=0;
// }
}
for (int j=1;j<=p;++j)
for (int i=1;i<=n;++i)
if (sum>k&&i%2==1&&j%2==1)
{
--sum;
a[i][j]=0;
}
for (int i=1;i<=n;++i)
if (i%2==1)
a[i][p+1]=1;
}
else
{
int sum=0;
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
if (i%2==1&&j%2==1&&k!=sum)
{
++sum;
a[i][j]=1;
}
// if (sum!=k)
// {u
// int inf=1e9+7;u
// for (int i=1;i<=um;++i)
// for (int j=0;j<=k;++j)
// for (int l=0;l<(1<<n);++l)
// f[i][j][l]=inf;
// for (int i=0;i<(1<<n);++i)
// if (__builtin_popcount(i)<=k)
// f[1][k-__builtin_popcount(i)][i]=0;
// for (int i=1;i<m;++i)
// for (int j=0;j<=k;++j)
// for (int l=0;l<(1<<n);++l)
// if (f[i][j][l]<inf)
// for
// }
// for (int i=1;i<=n;++i)
// for (int j=1;j<=m;++j)
// if (a[i][j]==0&&k!=0)
// {
// --k;
// a[i][j]=1;
// }
}
}
if (inv)
{
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
a[i][j]=!a[i][j];
}
if (trp)
{
for (int i=1;i<=m;++i)
{
for (int j=1;j<=n;++j)
printf("%d",a[j][i]);
puts("");
}
}
else
{
for (int i=1;i<=n;++i)
{
for (int j=1;j<=m;++j)
printf("%d",a[i][j]);
puts("");
}
}
}
int main()
{
for (int i=2;i<=8;++i)
for (int j=i;j<=8;++j)
for (int k=0;k<=i*j;++k)
prework(i,j,k,prea[i][j][k]);
scanf("%d",&t);
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 311ms
memory: 24304kb
input:
2 2 2 2 2 3 0
output:
10 01 000 000
result:
ok Output is valid. OK.
Test #2:
score: 0
Accepted
time: 467ms
memory: 24564kb
input:
27520 2 2 0 2 2 1 2 2 2 2 2 3 2 2 4 2 3 0 2 3 1 2 3 2 2 3 3 2 3 4 2 3 5 2 3 6 3 2 0 3 2 1 3 2 2 3 2 3 3 2 4 3 2 5 3 2 6 3 3 0 3 3 1 3 3 2 3 3 3 3 3 4 3 3 5 3 3 6 3 3 7 3 3 8 3 3 9 2 4 0 2 4 1 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 2 4 7 2 4 8 3 4 0 3 4 1 3 4 2 3 4 3 3 4 4 3 4 5 3 4 6 3 4 7 3 4 8 3 4 9 3 4 10...
output:
00 00 10 00 10 01 01 11 11 11 000 000 100 000 100 001 110 100 011 110 011 111 111 111 00 00 00 10 00 00 10 00 01 11 10 00 01 11 10 01 11 11 11 11 11 000 000 000 100 000 000 100 000 100 110 100 000 100 110 100 011 001 011 001 011 111 011 111 011 011 111 111 111 111 111 0000 0000 1000 0000 1010 0000 1...
result:
ok Output is valid. OK.
Test #3:
score: 0
Accepted
time: 453ms
memory: 30380kb
input:
162 2 2 2 2 3 2 2 3 3 2 3 4 3 2 2 3 2 3 3 2 4 3 3 2 3 3 3 3 3 4 3 3 5 3 3 6 3 3 7 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 3 4 2 3 4 3 3 4 4 3 4 5 3 4 6 3 4 7 3 4 8 3 4 9 3 4 10 4 2 2 4 2 3 4 2 4 4 2 5 4 2 6 4 3 2 4 3 3 4 3 4 4 3 5 4 3 6 4 3 7 4 3 8 4 3 9 4 3 10 4 4 2 4 4 3 4 4 4 4 4 5 4 4 6 4 4 7 4 4 8 4 4 9 ...
output:
10 01 100 001 110 100 011 110 10 00 01 11 10 00 01 11 10 100 000 100 110 100 000 100 110 100 011 001 011 001 011 111 011 111 011 1010 0000 1100 1000 1110 0100 0011 0111 0101 1111 1000 0000 1000 1100 1000 0000 1000 1100 1000 1100 1000 1100 1110 1100 1000 0011 0111 0011 0111 0011 0111 0011 0111 1111 0...
result:
ok Output is valid. OK.
Test #4:
score: 0
Accepted
time: 457ms
memory: 28396kb
input:
163 2 2 2 2 3 2 2 3 3 2 3 4 3 2 2 3 2 3 3 2 4 3 3 2 3 3 3 3 3 4 3 3 5 3 3 6 3 3 7 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 3 4 2 3 4 3 3 4 4 3 4 5 3 4 6 3 4 7 3 4 8 3 4 9 3 4 10 4 2 2 4 2 3 4 2 4 4 2 5 4 2 6 4 3 2 4 3 3 4 3 4 4 3 5 4 3 6 4 3 7 4 3 8 4 3 9 4 3 10 4 4 2 4 4 3 4 4 4 4 4 5 4 4 6 4 4 7 4 4 8 4 4 9 ...
output:
10 01 100 001 110 100 011 110 10 00 01 11 10 00 01 11 10 100 000 100 110 100 000 100 110 100 011 001 011 001 011 111 011 111 011 1010 0000 1100 1000 1110 0100 0011 0111 0101 1111 1000 0000 1000 1100 1000 0000 1000 1100 1000 1100 1000 1100 1110 1100 1000 0011 0111 0011 0111 0011 0111 0011 0111 1111 0...
result:
ok Output is valid. OK.
Test #5:
score: 0
Accepted
time: 455ms
memory: 28936kb
input:
165 2 2 2 2 3 2 2 3 3 2 3 4 3 2 2 3 2 3 3 2 4 3 3 2 3 3 3 3 3 4 3 3 5 3 3 6 3 3 7 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 3 4 2 3 4 3 3 4 4 3 4 5 3 4 6 3 4 7 3 4 8 3 4 9 3 4 10 4 2 2 4 2 3 4 2 4 4 2 5 4 2 6 4 3 2 4 3 3 4 3 4 4 3 5 4 3 6 4 3 7 4 3 8 4 3 9 4 3 10 4 4 2 4 4 3 4 4 4 4 4 5 4 4 6 4 4 7 4 4 8 4 4 9 ...
output:
10 01 100 001 110 100 011 110 10 00 01 11 10 00 01 11 10 100 000 100 110 100 000 100 110 100 011 001 011 001 011 111 011 111 011 1010 0000 1100 1000 1110 0100 0011 0111 0101 1111 1000 0000 1000 1100 1000 0000 1000 1100 1000 1100 1000 1100 1110 1100 1000 0011 0111 0011 0111 0011 0111 0011 0111 1111 0...
result:
ok Output is valid. OK.
Test #6:
score: 0
Accepted
time: 458ms
memory: 24308kb
input:
1020 2 2 2 2 3 2 2 3 3 2 3 4 3 2 2 3 2 3 3 2 4 3 3 2 3 3 3 3 3 4 3 3 5 3 3 6 3 3 7 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 3 4 2 3 4 3 3 4 4 3 4 5 3 4 6 3 4 7 3 4 8 3 4 9 3 4 10 4 2 2 4 2 3 4 2 4 4 2 5 4 2 6 4 3 2 4 3 3 4 3 4 4 3 5 4 3 6 4 3 7 4 3 8 4 3 9 4 3 10 4 4 2 4 4 3 4 4 4 4 4 5 4 4 6 4 4 7 4 4 8 4 4 9...
output:
10 01 100 001 110 100 011 110 10 00 01 11 10 00 01 11 10 100 000 100 110 100 000 100 110 100 011 001 011 001 011 111 011 111 011 1010 0000 1100 1000 1110 0100 0011 0111 0101 1111 1000 0000 1000 1100 1000 0000 1000 1100 1000 1100 1000 1100 1110 1100 1000 0011 0111 0011 0111 0011 0111 0011 0111 1111 0...
result:
ok Output is valid. OK.
Test #7:
score: 0
Accepted
time: 458ms
memory: 24488kb
input:
1012 2 2 2 2 3 2 2 3 3 2 3 4 3 2 2 3 2 3 3 2 4 3 3 2 3 3 3 3 3 4 3 3 5 3 3 6 3 3 7 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 3 4 2 3 4 3 3 4 4 3 4 5 3 4 6 3 4 7 3 4 8 3 4 9 3 4 10 4 2 2 4 2 3 4 2 4 4 2 5 4 2 6 4 3 2 4 3 3 4 3 4 4 3 5 4 3 6 4 3 7 4 3 8 4 3 9 4 3 10 4 4 2 4 4 3 4 4 4 4 4 5 4 4 6 4 4 7 4 4 8 4 4 9...
output:
10 01 100 001 110 100 011 110 10 00 01 11 10 00 01 11 10 100 000 100 110 100 000 100 110 100 011 001 011 001 011 111 011 111 011 1010 0000 1100 1000 1110 0100 0011 0111 0101 1111 1000 0000 1000 1100 1000 0000 1000 1100 1000 1100 1000 1100 1110 1100 1000 0011 0111 0011 0111 0011 0111 0011 0111 1111 0...
result:
ok Output is valid. OK.
Test #8:
score: 0
Accepted
time: 455ms
memory: 24412kb
input:
1033 2 2 2 2 3 2 2 3 3 2 3 4 3 2 2 3 2 3 3 2 4 3 3 2 3 3 3 3 3 4 3 3 5 3 3 6 3 3 7 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 3 4 2 3 4 3 3 4 4 3 4 5 3 4 6 3 4 7 3 4 8 3 4 9 3 4 10 4 2 2 4 2 3 4 2 4 4 2 5 4 2 6 4 3 2 4 3 3 4 3 4 4 3 5 4 3 6 4 3 7 4 3 8 4 3 9 4 3 10 4 4 2 4 4 3 4 4 4 4 4 5 4 4 6 4 4 7 4 4 8 4 4 9...
output:
10 01 100 001 110 100 011 110 10 00 01 11 10 00 01 11 10 100 000 100 110 100 000 100 110 100 011 001 011 001 011 111 011 111 011 1010 0000 1100 1000 1110 0100 0011 0111 0101 1111 1000 0000 1000 1100 1000 0000 1000 1100 1000 1100 1000 1100 1110 1100 1000 0011 0111 0011 0111 0011 0111 0011 0111 1111 0...
result:
ok Output is valid. OK.
Test #9:
score: 0
Accepted
time: 467ms
memory: 24528kb
input:
100000 2 2 2 2 3 2 2 3 3 2 3 4 3 2 2 3 2 3 3 2 4 3 3 2 3 3 3 3 3 4 3 3 5 3 3 6 3 3 7 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 3 4 2 3 4 3 3 4 4 3 4 5 3 4 6 3 4 7 3 4 8 3 4 9 3 4 10 4 2 2 4 2 3 4 2 4 4 2 5 4 2 6 4 3 2 4 3 3 4 3 4 4 3 5 4 3 6 4 3 7 4 3 8 4 3 9 4 3 10 4 4 2 4 4 3 4 4 4 4 4 5 4 4 6 4 4 7 4 4 8 4 4...
output:
10 01 100 001 110 100 011 110 10 00 01 11 10 00 01 11 10 100 000 100 110 100 000 100 110 100 011 001 011 001 011 111 011 111 011 1010 0000 1100 1000 1110 0100 0011 0111 0101 1111 1000 0000 1000 1100 1000 0000 1000 1100 1000 1100 1000 1100 1110 1100 1000 0011 0111 0011 0111 0011 0111 0011 0111 1111 0...
result:
ok Output is valid. OK.
Test #10:
score: 0
Accepted
time: 379ms
memory: 24396kb
input:
100000 2 2 2 2 3 2 2 3 3 2 3 4 3 2 2 3 2 3 3 2 4 3 3 2 3 3 3 3 3 4 3 3 5 3 3 6 3 3 7 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 3 4 2 3 4 3 3 4 4 3 4 5 3 4 6 3 4 7 3 4 8 3 4 9 3 4 10 4 2 2 4 2 3 4 2 4 4 2 5 4 2 6 4 3 2 4 3 3 4 3 4 4 3 5 4 3 6 4 3 7 4 3 8 4 3 9 4 3 10 4 4 2 4 4 3 4 4 4 4 4 5 4 4 6 4 4 7 4 4 8 4 4...
output:
10 01 100 001 110 100 011 110 10 00 01 11 10 00 01 11 10 100 000 100 110 100 000 100 110 100 011 001 011 001 011 111 011 111 011 1010 0000 1100 1000 1110 0100 0011 0111 0101 1111 1000 0000 1000 1100 1000 0000 1000 1100 1000 1100 1000 1100 1110 1100 1000 0011 0111 0011 0111 0011 0111 0011 0111 1111 0...
result:
ok Output is valid. OK.
Test #11:
score: 0
Accepted
time: 378ms
memory: 24384kb
input:
100000 2 2 2 2 3 2 2 3 3 2 3 4 3 2 2 3 2 3 3 2 4 3 3 2 3 3 3 3 3 4 3 3 5 3 3 6 3 3 7 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 3 4 2 3 4 3 3 4 4 3 4 5 3 4 6 3 4 7 3 4 8 3 4 9 3 4 10 4 2 2 4 2 3 4 2 4 4 2 5 4 2 6 4 3 2 4 3 3 4 3 4 4 3 5 4 3 6 4 3 7 4 3 8 4 3 9 4 3 10 4 4 2 4 4 3 4 4 4 4 4 5 4 4 6 4 4 7 4 4 8 4 4...
output:
10 01 100 001 110 100 011 110 10 00 01 11 10 00 01 11 10 100 000 100 110 100 000 100 110 100 011 001 011 001 011 111 011 111 011 1010 0000 1100 1000 1110 0100 0011 0111 0101 1111 1000 0000 1000 1100 1000 0000 1000 1100 1000 1100 1000 1100 1110 1100 1000 0011 0111 0011 0111 0011 0111 0011 0111 1111 0...
result:
ok Output is valid. OK.
Test #12:
score: 0
Accepted
time: 442ms
memory: 32132kb
input:
3 1500 1500 2250000 1322 1322 1747684 1158 2 2316
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Output is valid. OK.
Test #13:
score: 0
Accepted
time: 454ms
memory: 32544kb
input:
3 1500 1500 1125000 1322 1322 873842 1158 2 1158
output:
011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Output is valid. OK.
Extra Test:
score: 0
Extra Test Passed