QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #350186 | #8217. King's Dinner | ucup-team1525# | WA | 1ms | 4580kb | C++17 | 4.0kb | 2024-03-10 15:09:49 | 2024-03-10 15:09:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int t,n;
const int N=105;
int sum[N],f[N];
char s[N][N][N];
int calc(int n)
{
int p=0,sum=0,la=-1;
for (int i=1;i<=4;++i)
for (int j=1;j<=n-1;++j)
{
++p;
if (p%3==1)
{
if (la==n-2&&j==2)
--p;
else
{
++sum;
la=j;
}
}
}
if (p%3==1)
--sum;
return sum;
}
void prework()
{
for (int n=1;n<=100;++n)
{
int ans=0,l=0;
for (int i=0;i*3-1<=n;++i)
{
int sum1=(n+1)/2*i;
int down=n-i*3+1;
int downp=down/2;
int sum2=(n+1)/3*downp;
if (sum1+sum2>=ans)
{
ans=sum1+sum2;
l=i;
}
}
sum[n]=ans;
f[n]=l;
// if (n<=10)cout<<n<<' '<<sum[n]<<' '<<f[n]<<endl;
}
for (int n=4;n<=100;++n)
{
int newf=sum[n-4]+calc(n);
if (newf>sum[n])
{
// cout<<"!"<<n<<' '<<sum[n]<<' '<<newf<<endl;
sum[n]=newf;
f[n]=-1;
}
}
}
void build(int n)
{
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
s[n][i][j]='.';
if (f[n]==-1)
{
// build(n-4);
// for (int i=n-4;i;--i)
// for (int j=n-4;j;--j)
// s[i+2][j+2]=s[i][j];
// for (int i=1;i<=n;++i)
// s[1][i]=s[2][i]=s[i][1]=s[i][2]='.';
for (int i=1;i<=n-4;++i)
for (int j=1;j<=n-4;++j)
s[n][i+2][j+2]=s[n-4][i][j];
int p=0,la=-1;
for (int i=1;i<=n-1;++i)
{
++p;
if (p%3!=0)
{
s[n][1][i]='#';
la=i;
}
}
for (int i=1;i<=n-1;++i)
{
++p;
if (p%3!=0)
{
if (i==2&&la==n-1)
{
--p;
}
else
{
s[n][i][n]='#';
la=i;
}
}
}
for (int i=n;i>=2;--i)
{
++p;
if (p%3!=0)
{
if (i==n-1&&la==n-1)
{
--p;
}
else
{
s[n][n][i]='#';
la=i;
}
}
}
for (int i=n;i>=3;--i)
{
++p;
if (p%3!=0&&(p%3==2||i!=3))
{
if (i==n-1&&la==2)
{
--p;
}
else
{
s[n][i][1]='#';
la=i;
}
}
}
}
else
{
int l=f[n];
int p=1;
for (int i=1;i<=l;++i)
{
for (int j=1;j<=n;++j)
if (j%2==1)
s[n][p][j]='#';
++p;
for (int j=1;j<=n;++j)
if (j%2==1)
s[n][p][j]='#';
++p;
++p;
}
int r=(n-l*3+1)/2;
for (int i=1;i<=r;++i)
{
for (int j=1;j<=n;++j)
if (j%3!=0&&(j!=n||n%3==2))
s[n][p][j]='#';
++p;
++p;
}
}
}
int main()
{
prework();
scanf("%d",&t);
for (int i=1;i<=100;++i)
build(i);
while (t--)
{
scanf("%d",&n);
// n=100;
// build(n);
for (int i=1;i<=n;++i)
{
for (int j=1;j<=n;++j)
putchar(s[n][i][j]);
putchar('\n');
}
// cout<<(double)ans/(double)n/(double)n<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4560kb
input:
3 1 2 3
output:
. #. #. #.# #.# ...
result:
ok all tests correct (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 4580kb
input:
50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
output:
. #. #. #.# #.# ... ##.# ...# #... #.## #.#.# #.#.# ..... #.#.# #.#.# #.#.#. #.#.#. ...... ##.##. ...... ##.##. #.#.#.# #.#.#.# ....... #.#.#.# #.#.#.# ....... ##.##.. #.#.#.#. #.#.#.#. ........ ##.##.## ........ ##.##.## ........ ##.##.## #.#.#.#.# #.#.#.#.# ......... #.#.#.#.# #.#.#.#.# ......... ...
result:
wrong answer jury has the better answer: jans = 8, pans = 7 (test case 6)