QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#334017#4325. Kraljicecoolplum0 1ms3756kbC++1711.1kb2024-02-20 23:32:222024-02-20 23:32:23

Judging History

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

  • [2024-02-20 23:32:23]
  • 评测
  • 测评结果：0
  • 用时：1ms
  • 内存：3756kb
查看
  • [2024-02-20 23:32:22]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1025;

int n;
int row[MAXN]={0}, column[MAXN]={0}, ldiagonal[2*MAXN]={0}, rdiagonal[2*MAXN]={0};
int order[MAXN][MAXN];
int k=1;

void add(int x, int y)
{
    order[x][y]=k;
    k=k+1;
    row[x]=row[x]+1;
    column[y]=column[y]+1;
    ldiagonal[x+y]=ldiagonal[x+y]+1;
    rdiagonal[x-y+n]=rdiagonal[x-y+n]+1;

    return;
}

void build3(int x, int y)
{
    if (y==1)
    {
        add(1, 2);
        add(2, 0);
        add(1, 1);
        add(0, 0);
        add(2, 2);
        add(2, 1);
        add(0, 1);
        add(0, 2);
        add(1, 0);

        return;
    }
    if (x==0)
        build3(x, y-2);
    if (y-x==1)
    {
        y=y-1;
        add(x+1, y+2);
        add(x+0, y+1);
        add(x+2, y+1);
        add(x+1, y+1);
        add(x+0, y+2);
        add(x+2, y+0);
        add(x+1, y+0);
        add(x+2, y+2);

        return;
    }
    if ((row[x]+column[y]+ldiagonal[x+y]+rdiagonal[x-y+n])%2==0)
    {
        add(x, y);
        add(x, y+1);
        if ((row[y]+column[x]+ldiagonal[y+x]+rdiagonal[y-x+n])%2==0)
        {
            add(y, x);
            add(y+1, x);
        }
        else
        {
            add(y+1, x);
            add(y, x);
        }
    }
    else
    {
        add(x, y+1);
        add(x, y);
        if ((row[y]+column[x]+ldiagonal[y+x]+rdiagonal[y-x+n])%2==0)
        {
            add(y, x);
            add(y+1, x);
        }
        else
        {
            add(y+1, x);
            add(y, x);
        }
    }
    build3(x+1, y);

    return;
}

void build4(int x, int y)
{
    if (y==2)
    {
        add(0, 1);
        add(1, 3);
        add(0, 2);
        add(1, 0);
        add(1, 1);
        add(2, 3);
        add(0, 3);
        add(2, 0);
        add(2, 1);
        add(2, 2);
        add(3, 0);
        add(3, 2);
        add(3, 1);
        add(3, 3);

        return;
    }
    if (x==0)
        build4(x, y-2);
    if (y-x==1)
    {
        y=y-1;
        add(x+0, y+2);
        add(x+0, y+1);
        add(x+1, y+2);
        add(x+1, y+0);
        add(x+2, y+0);
        add(x+1, y+1);
        add(x+2, y+1);
        add(x+2, y+2);

        return;
    }
    //cout << "x " << x+1 << ' ' << y+1 << '\n';
    //cout << row[x]+column[y]+ldiagonal[x+y]+rdiagonal[x-y+n] << '\n';
    if ((row[x]+column[y]+ldiagonal[x+y]+rdiagonal[x-y+n])%2==0)
    {
        add(x, y);
        add(x, y+1);
        //cout << "x " << y+1 << ' ' << x+1 << '\n';
        //cout << row[y]+column[x]+ldiagonal[x+y]+rdiagonal[y-x+n] << '\n';
        if ((row[y]+column[x]+ldiagonal[y+x]+rdiagonal[y-x+n])%2==0)
        {
            add(y, x);
            add(y+1, x);
        }
        else
        {
            add(y+1, x);
            add(y, x);
        }
    }
    else
    {
        add(x, y+1);
        add(x, y);
        //cout << "x " << y+1 << ' ' << x+1 << '\n';
        //cout << row[y]+column[x]+ldiagonal[x+y]+rdiagonal[y-x+n] << '\n';
        if ((row[y]+column[x]+ldiagonal[y+x]+rdiagonal[y-x+n])%2==0)
        {
            add(y, x);
            add(y+1, x);
        }
        else
        {
            add(y+1, x);
            add(y, x);
        }
    }
    build4(x+1, y);

    return;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            order[i][j]=0;
    if (n<=2)
    {
        cout << 1 << '\n';
        cout << 1 << ' ' << 1 << '\n';
    }
    else if (n%2==1)
    {
        build3(0, n-2);
        pair<int, int> answer[n*n];
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                answer[order[i][j]-1]={i+1, j+1};
        cout << n*n << '\n';
        for (int i=0; i<n*n; i++)
            cout << answer[i].first << ' ' << answer[i].second << '\n';
    }
    else
    {
        build4(0, n-2);
        pair<int, int> answer[n*n-2];
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                if (order[i][j]!=0)
                    answer[order[i][j]-1]={i+1, j+1};
        cout << n*n-2 << '\n';
        for (int i=0; i<n*n-2; i++)
            cout << answer[i].first << ' ' << answer[i].second << '\n';
    }

    return 0;
}


/*#include <bits/stdc++.h>
using namespace std;

int n=5;
bool a[5][5];
int b[5][5];
bool found=false, k=1;


void buildx(int x, int k)
{
    if (found)
        return;
    if (x==n-2)
    {
        found=true;
        return;
    }
    int xt=x, yt=n-2;
    int kraljice=0;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            if (a[i][j]==1 && (i==xt || j==yt || abs(xt-i)==abs(yt-j)))
                kraljice=kraljice+1;
    if (kraljice%2==0)
    {
        a[xt][yt]=1;
        b[xt][yt]=k;
        xt=x, yt=n-1;
        kraljice=0;
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                if (a[i][j]==1 && (i==xt || j==yt || abs(xt-i)==abs(yt-j)))
                    kraljice=kraljice+1;
        if (kraljice%2==0)
        {
            a[xt][yt]=1;
            b[xt][yt]=k+1;
            buildx(x+1, k+2);
        }
    }
    if (found)
        return;
    a[x][n-1]=0;
    a[x][n-2]=0;
    b[x][n-1]=0;
    b[x][n-2]=0;

    xt=x, yt=n-1;
    kraljice=0;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            if (a[i][j]==1 && (i==xt || j==yt || abs(xt-i)==abs(yt-j)))
                kraljice=kraljice+1;
    if (kraljice%2==0)
    {
        a[xt][yt]=1;
        b[xt][yt]=k;
        xt=x, yt=n-2;
        kraljice=0;
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                if (a[i][j]==1 && (i==xt || j==yt || abs(xt-i)==abs(yt-j)))
                    kraljice=kraljice+1;
        if (kraljice%2==0)
        {
            a[xt][yt]=1;
            b[xt][yt]=k+1;
            buildx(x+1, k+2);
        }
    }
    if (found)
        return;
    a[x][n-1]=0;
    a[x][n-2]=0;
    b[x][n-1]=0;
    b[x][n-2]=0;

    return;
}

void buildy(int x, int k)
{
    if (found)
        return;
    if (x==n-2)
    {
        found=true;
        return;
    }
    cout << "x " << x << '\n';
    int xt=n-1, yt=x;
    int kraljice=0;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            if (a[i][j]==1 && (i==xt || j==yt || abs(xt-i)==abs(yt-j)))
                kraljice=kraljice+1;
    if (kraljice%2==0)
    {
        a[xt][yt]=1;
        b[xt][yt]=k;
        xt=n-1, yt=x;
        kraljice=0;
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                if (a[i][j]==1 && (i==xt || j==yt || abs(xt-i)==abs(yt-j)))
                    kraljice=kraljice+1;
        if (kraljice%2==0)
        {
            a[xt][yt]=1;
            b[xt][yt]=k+1;
            buildy(x+1, k+2);
        }
    }
    a[n-1][x]=0;
    a[n-2][x]=0;
    b[n-1][x]=0;
    b[n-2][x]=0;

    if (found)
        return;
    xt=n-1, yt=x;
    kraljice=0;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            if (a[i][j]==1 && (i==xt || j==yt || abs(xt-i)==abs(yt-j)))
                kraljice=kraljice+1;
    if (kraljice%2==0)
    {
        a[xt][yt]=1;
        b[xt][yt]=k;
        xt=n-2, yt=x;
        kraljice=0;
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                if (a[i][j]==1 && (i==xt || j==yt || abs(xt-i)==abs(yt-j)))
                    kraljice=kraljice+1;
        if (kraljice%2==0)
        {
            a[xt][yt]=1;
            b[xt][yt]=k+1;
            buildy(x+1, k+2);
        }
    }
    a[n-1][x]=0;
    a[n-2][x]=0;
    b[n-1][x]=0;
    b[n-2][x]=0;

    return;
}

int main()
{
    memset(a, 0, sizeof(a));
    for (int i=0; i<3; i++)
        for (int j=0; j<3; j++)
            a[i][j]=1;
    memset(b, 0, sizeof(b));
    buildy(0, 1);
    found=false;
    buildx(0, 1);
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }

    return 0;
}*/


/*#include <bits/stdc++.h>
using namespace std;

int n=5;
bool a[5][5];
pair<int, int> adjy[]={{0,-1},{1,0},{0,1},{-1,2}};
pair<int, int> adjx[]={{-1,0},{0,1},{1,0},{2,-1}};
pair<int, int> perm[]={{0,0},{0,-1},{-1,0},{-1,-1}};
bool good;
int pt;

void buildy(int x, int y, int t)
{
    if (!good)
        return;
    if (x==n || y==n)
        return;
    if (y>=n-2)
        return;
    for (int i=0; i<5; i++)
    {
        for (int j=0; j<5; j++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }
    cout << '\n';
    int kraljice=0;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            if (a[i][j]==1 && (i==x || j==y || abs(x-i)==abs(y-j)))
                kraljice=kraljice+1;
    while (kraljice%2==1)
    {
        if (kraljice%2==1 && pt==4)
        {
            good=false;
            return;
        }
        int xt=n-1+perm[pt].first;
        int yt=n-1+perm[pt].second;
        a[xt][yt]=1;
        if (xt==x || xt==y || abs(x-xt)==abs(y-yt))
            kraljice=kraljice+1;
        pt=pt+1;
    }
    a[x][y]=1;
    int xt, yt;
    if (x==4 && y==1)
    {
        xt=4;
        yt=2;
    }
    else if (x==4 && y==2)
    {
        xt=3;
        yt=2;
    }
    else if (x==3 && y==2)
        return;
    else
    {
        xt=x+adjy[t].first;
        yt=y+adjy[t].second;
    }
    buildy(xt, yt, (t+1)%4);

    return;
}

void buildx(int x, int y, int t)
{
    if (!good)
        return;
    if (x==n || y==n)
        return;
    if (x>=n-2)
        return;
    for (int i=0; i<5; i++)
    {
        for (int j=0; j<5; j++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }
    cout << '\n';
    int kraljice=0;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            if (a[i][j]==1 && (i==x || j==y || abs(x-i)==abs(y-j)))
                kraljice=kraljice+1;
    while (kraljice%2==1)
    {
        if (kraljice%2==1 && pt==4)
        {
            good=false;
            return;
        }
        int xt=n-1+perm[pt].first;
        int yt=n-1+perm[pt].second;
        a[xt][yt]=1;
        if (xt==x || xt==y || abs(x-xt)==abs(y-yt))
            kraljice=kraljice+1;
        pt=pt+1;
    }
    a[x][y]=1;
    int xt, yt;
    if (x==1 && y==4)
    {
        xt=2;
        yt=4;
    }
    else if (x==2 && y==4)
    {
        xt=2;
        yt=3;
    }
    else if (x==2 && y==3)
        return;
    else
    {
        xt=x+adjx[t].first;
        yt=y+adjx[t].second;
    }
    buildx(xt, yt, (t+1)%4);

    return;
}

int main()
{
    sort(perm, perm+4);
    int total=0;
    do {
        memset(a, 0, sizeof(a));
        for (int i=0; i<3; i++)
            for (int j=0; j<3; j++)
                a[i][j]=1;
        good=true;
        pt=0;
        buildy(3, 1, 0);
        buildx(1, 3, 0);
        if (good)
            total=total+1;
    } while (next_permutation(perm, perm+4));
    cout << total << '\n';

    return 0;
}*/
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 6
Accepted
time: 0ms
memory: 3644kb

input:

1

output:

1
1 1

result:

ok 1 queen(s)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

2

output:

1
1 1

result:

ok 1 queen(s)

Test #3:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

3

output:

9
2 3
3 1
2 2
1 1
3 3
3 2
1 2
1 3
2 1

result:

ok 9 queen(s)

Test #4:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

4

output:

14
1 2
2 4
1 3
2 1
2 2
3 4
1 4
3 1
3 2
3 3
4 1
4 3
4 2
4 4

result:

ok 14 queen(s)

Test #5:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

5

output:

25
2 3
3 1
2 2
1 1
3 3
3 2
1 2
1 3
2 1
1 5
1 4
4 1
5 1
2 4
2 5
5 2
4 2
4 5
3 4
5 4
4 4
3 5
5 3
4 3
5 5

result:

ok 25 queen(s)

Test #6:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

6

output:

34
1 2
2 4
1 3
2 1
2 2
3 4
1 4
3 1
3 2
3 3
4 1
4 3
4 2
4 4
1 5
1 6
6 1
5 1
2 6
2 5
6 2
5 2
3 6
3 5
6 3
5 3
4 6
4 5
5 6
5 4
6 4
5 5
6 5
6 6

result:

ok 34 queen(s)

Test #7:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

7

output:

49
2 3
3 1
2 2
1 1
3 3
3 2
1 2
1 3
2 1
1 5
1 4
4 1
5 1
2 4
2 5
5 2
4 2
4 5
3 4
5 4
4 4
3 5
5 3
4 3
5 5
1 7
1 6
6 1
7 1
2 6
2 7
7 2
6 2
3 7
3 6
6 3
7 3
4 6
4 7
7 4
6 4
6 7
5 6
7 6
6 6
5 7
7 5
6 5
7 7

result:

ok 49 queen(s)

Test #8:

score: -6
Wrong Answer
time: 1ms
memory: 3756kb

input:

8

output:

62
1 2
2 4
1 3
2 1
2 2
3 4
1 4
3 1
3 2
3 3
4 1
4 3
4 2
4 4
1 5
1 6
6 1
5 1
2 6
2 5
6 2
5 2
3 6
3 5
6 3
5 3
4 6
4 5
5 6
5 4
6 4
5 5
6 5
6 6
1 7
1 8
8 1
7 1
2 8
2 7
8 2
7 2
3 8
3 7
8 3
7 3
4 7
4 8
8 4
7 4
5 8
5 7
8 5
7 5
6 8
6 7
7 8
7 6
8 6
7 7
8 7
8 8

result:

wrong answer the cell (8, 5) is attacking by 15 queen(s)

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2024-12-02 13:07:57 | OpenSource Project