QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#267007#7740. Puzzle: Question Markucup-team2307#WA 203ms26360kbC++178.5kb2023-11-26 21:03:172023-11-26 21:03:17

Judging History

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

  • [2023-11-26 21:03:17]
  • 评测
  • 测评结果：WA
  • 用时：203ms
  • 内存：26360kb
查看
  • [2023-11-26 21:03:17]
  • 提交

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
*/
源文件, 语言: C++17

详细

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)
English 繁體中文 简体中文

服务器时间: 2024-12-12 02:58:03 | 开源项目