QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #267007 | #7740. Puzzle: Question Mark | ucup-team2307# | WA | 203ms | 26360kb | C++17 | 8.5kb | 2023-11-26 21:03:17 | 2023-11-26 21:03:17 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
typedef long long ll;
#define int ll
using namespace std;
vector<pair<int, int> > moves = { {0, 0}, {1, 0}, {0, 1}, {2, 1} };
vector<vector<pair<int, int> > > m;
int n;
const int N = 5050;
int a[N][N];
map<int, vector<vector<int> > > mp;
int gmask;
vector<vector<int> > geta()
{
vector<vector<int> > ar;
ar.resize(n);
for (int i=0; i<n; i++)
{
ar[i].resize(n);
for (int j=0; j<n; j++)
ar[i][j] = a[i][j];
}
return ar;
}
int getmask()
{
int m = 0;
for (int i=0; i<5; i++)
m *= 2, m += (a[n-1][n-1-i] != 0);//, m *= 2, m += (a[n-2][n-1-i] != 0);
for (int i=0; i<5; i++)
m *= 2, m += (a[n-1-i][n-1] != 0);//, m *= 2, m += (a[n-1-i][n-2] != 0);
return m;
}
bool okey(int x)
{
return (x >= 0) && (x < n);
}
void brute(int x, int y, int cnt)
{
if (y == n)
{
brute(x+1, 0, cnt);
return;
}
if (x == n)
{
if (n == 5)
{
// bool ok = true;
// for (int i=0; i<n-1; i++)
// for (int j=0; j<n-1; j++)
// if (a[i][j] == 0)
// ok = false;
// if (!ok)
// return;
if (cnt == 5)
mp[getmask()] = geta();
return;
}
int bad = 0;
for (int i=0; i<n-1; i++)
for (int j=0; j<n-1; j++)
if (a[i][j] == 0)
bad++;
if (cnt < 9)
return;
if (getmask() != gmask)
// if (!mp.count(getmask()))
return;
// for (int i=0; i<5; i++, cout<<endl)
// for (int j=0; j<5; j++)
// cout<<mp[getmask()][i][j]<<" ";
// cout<<endl;
for (int i=0; i<n; i++, cout<<endl)
for (int j=0; j<n; j++)
cout<<setw(2)<<a[i][j]<<" ";
cout<<endl;
// if (cnt >= 9)
exit(1);
return;
}
for (auto v : m)
{
bool ok = true;
for (auto pa : v)
if (!okey(x+pa.fi) || !okey(y+pa.se) || a[x+pa.fi][y+pa.se]!=0)
ok = false;
if (ok)
{
for (auto pa : v)
a[x+pa.fi][y+pa.se]=cnt+1;
brute(x, y+1, cnt+1);
for (auto pa : v)
a[x+pa.fi][y+pa.se]=0;
}
}
brute(x, y+1, cnt);
}
int cnt;
void fillrect(int x, int y, int dx, int dy)
{
if (dx == 2)
{
cnt++;
a[x][y] = cnt;
a[x+1][y] = cnt;
a[x+1][y+1] = cnt;
a[x][y+2] = cnt;
cnt++;
a[x][y+1] = cnt;
a[x][y+3] = cnt;
a[x+1][y+2] = cnt;
a[x+1][y+3] = cnt;
}
else
{
cnt++;
a[x][y] = cnt;
a[x][y+1] = cnt;
a[x+1][y+1] = cnt;
a[x+2][y] = cnt;
cnt++;
a[x+1][y] = cnt;
a[x+3][y] = cnt;
a[x+2][y+1] = cnt;
a[x+3][y+1] = cnt;
}
}
void solve()
{
int n;
cin>>n;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
a[i][j] = 0;
cnt = 0;
if (n <= 2)
{
cnt = 0;
}
else
if (n%2 == 0)
{
for (int i=0; i+4<=n; i+=4)
for (int j=0; j+2<=n; j+=2)
fillrect(i, j, 4, 2);
if (n%4 == 2)
{
for (int j=0; j+4<=n; j+=4)
fillrect(n-2, j, 2, 4);
}
}
else if (n == 3)
{
cout<<"2\n1 1 0\n";
cout<<"1 2 2\n";
cout<<"2 1 2\n";
}
else
{
int sx = N/2, sy = N/2;
vector<vector<int> > v =
{{1, 1, 2, 2, 3, -1, -1, -1, -1},
{0, 1, 2, 3, 2, -1, -1, -1, -1},
{1, 4, 4, 3, 3, 6, 6, -1, -1},
{5, 4, 5, 4, 7, 7, 6, -1, -1},
{5, 5, 8, 8, 7, 6, 9, 10, 9},
{-1,-1, 8, 11, 11, 7, 9, 9, 10},
{-1,-1,11, 8, 11, 12, 12, 10, 10},
{-1,-1,-1, -1, 13, 12, 13, 12, 0},
{-1,-1,-1, -1, 13, 13, 0, 0, 0}};
v = {
{ 0, 1, 1, 2, 2, -1, -1},
{ 3, 1, 3, 1, 2, -1, -1},
{ 3, 3, 4, 2, 4, 6, 6},
{ 5, 0, 5, 4, 4, 7, 6},
{ 5, 5, 8, 9, 9, 6, 7},
{-1, -1, 9, 8, 9, 7, 7},
{-1, -1, 8, 8, 0, 0, 0},
};
int curx = N/2;
int cury = N/2;
for (int i=0; i<5; i++)
for (int j=0; j<5; j++)
if (v[i][j] <= 5)
a[curx+i][cury+j] = v[i][j];
cnt = 5;
int curn = 5;
while (curn + 4 <= n)
{
curx -= 2;
cury -= 2;
curn += 4;
cnt++;
a[curx][cury] = cnt;
a[curx+1][cury+1] = cnt;
a[curx+2][cury] = cnt;
a[curx+2][cury+1] = cnt;
cnt++;
a[curx][cury+1] = cnt;
a[curx+1][cury] = cnt;
a[curx][cury+2] = cnt;
a[curx+1][cury+2] = cnt;
for (int i=3; i+4<=curn; i+=4)
{
fillrect(curx+0, cury+i, 2, 4);
fillrect(curx+i, cury+0, 4, 2);
}
for (int i=0; i+8<=curn; i+=4)
{
fillrect(curx+i, cury+curn-2, 4, 2);
fillrect(curx+curn-2, cury+i, 2, 4);
}
for (int i=0; i<7; i++)
for (int j=0; j<7; j++)
if (v[i][j] >= 6)
{
a[curx+curn-7+i][cury+curn-7+j] = v[i][j] - 6 + cnt + 1;
}
cnt += 4;
}
if (n == curn + 2)
{
curx -= 2;
cury -= 2;
curn += 2;
cnt++;
a[curx][cury] = cnt;
a[curx+1][cury+1] = cnt;
a[curx+2][cury] = cnt;
a[curx+2][cury+1] = cnt;
cnt++;
a[curx][cury+1] = cnt;
a[curx+1][cury] = cnt;
a[curx][cury+2] = cnt;
a[curx+1][cury+2] = cnt;
for (int i=3; i+4<=curn; i+=4)
{
fillrect(curx+0, cury+i, 2, 4);
fillrect(curx+i, cury+0, 4, 2);
}
}
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
a[i][j] = a[i+curx][j+cury];
}
if (n != 3)
{
cout<<cnt<<"\n";
for (int i=0; i<n; i++, cout<<"\n")
for (int j=0; j<n; j++)
{
cout<<a[i][j];
// cout<<setw(2)<<a[i][j];
if (j != n-1)
cout<<" ";
}
}
}
main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while (t--)
solve();
return 0;
for (int bx = -1; bx <= 1; bx+=2)
for (int by = -1; by <= 1; by+=2)
{
vector<pair<int, int> > m0;
for (auto p : moves)
m0.pb({p.fi*bx, p.se*by});
m.pb(m0);
m.pb(m0);
for (auto& p : m.back())
swap(p.fi, p.se);
}
for (auto& v : m)
{
pair<int, int> mx = {10, 0};
for (auto pa : v)
mx = min(mx, pa);
for (auto& pa : v)
pa.fi -= mx.fi, pa.se -= mx.se;
for (auto pa : v)
cout<<pa.fi<<" "<<pa.se<<", ";
cout<<"\n";
}
n = 5;
brute(0, 0, 0);
cout<<"n=5"<<endl;
n = 7;
for (auto pa : mp)
{
gmask = pa.fi;
cout<<gmask<<endl;
for (int i=0; i<2; i++)
for (int j=0; j<2; j++)
a[0+i][5+j] = a[0+i][7+j] = a[2+i][7+j] = -1,
a[5+i][0+j] = a[7+i][0+j] = a[7+i][2+j] = -1;
// for (int i=0; i<7; i++)
// for (int j=0; j<2; j++)
// a[i][j] = a[j][i] = -1;
for (int i=0; i<5; i++)
for (int j=0; j<5; j++)
a[i][j] = pa.se[i][j];
brute(0, 0, 5);
for (int i=0; i<5; i++, cout<<endl)
for (int j=0; j<5; j++)
cout<<pa.se[i][j]<<" ";
for (int i=0; i<n; i++, cout<<endl)
for (int j=0; j<n; j++)
cout<<setw(2)<<a[i][j]<<" ";
cout<<"nope"<<endl;
}
}
/*
1 1 2 2 3 -1 -1 -1 -1
0 1 2 3 2 -1 -1 -1 -1
1 4 4 3 3 6 6 -1 -1
5 4 5 4 7 7 6 -1 -1
5 5 8 8 7 6 9 10 9
-1 -1 8 11 11 7 9 9 10
-1 -1 11 8 11 12 12 10 10
-1 -1 -1 -1 13 12 13 12 0
-1 -1 -1 -1 13 13 0 0 0
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5904kb
input:
2 3 4
output:
2 1 1 0 1 2 2 2 1 2 4 1 1 3 3 2 1 4 3 1 2 3 4 2 2 4 4
result:
ok Correct. (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 203ms
memory: 26360kb
input:
246 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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
output:
0 0 0 0 0 0 0 2 1 1 0 1 2 2 2 1 2 4 1 1 3 3 2 1 4 3 1 2 3 4 2 2 4 4 5 0 1 1 2 2 3 1 3 1 2 3 3 4 2 4 5 0 5 4 4 5 5 0 0 0 8 1 1 3 3 5 5 2 1 4 3 6 5 1 2 3 4 5 6 2 2 4 4 6 6 7 8 7 8 0 0 7 7 8 8 0 0 11 6 7 7 8 9 8 9 7 6 7 8 8 9 9 6 6 0 1 1 2 2 10 10 3 1 3 1 2 11 10 3 3 4 2 4 10 11 5 0 5 4 4 11 11 5 5 0 0...
result:
wrong answer Jury has better answer. Participant 19, jury 20 (test case 9)