QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#333975#4325. Kraljicecoolplum0 1ms7736kbC++149.9kb2024-02-20 22:08:292024-02-20 22:08:30

Judging History

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

  • [2024-02-20 22:08:30]
  • 评测
  • 测评结果：0
  • 用时：1ms
  • 内存：7736kb
查看
  • [2024-02-20 22:08:29]
  • 提交

answer

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

const int MAXN=1025;

int n;
int row[MAXN]={0}, column[MAXN]={0}, diagonal[4*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;
    diagonal[x+y]=diagonal[x+y]+1;
    diagonal[x-y+n]=diagonal[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]+diagonal[x+y]+diagonal[x-y+n])%2==0)
    {
        add(x, y);
        add(x, y+1);
        add(y+1, x);
        add(y, x);
    }
    else
    {
        add(x, y+1);
        add(x, y);
        add(y, x);
        add(y+1, 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;
    }
    if ((row[x]+column[y]+diagonal[x+y]+diagonal[x-y+n])%2==0)
    {
        add(x, y);
        add(x, y+1);
        add(y+1, x);
        add(y, x);
    }
    else
    {
        add(x, y+1);
        add(x, y);
        add(y, x);
        add(y+1, x);
    }
    build4(x+1, y);

    return;
}

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

    int n;
    cin >> n;
    memset(order, 0, sizeof(order));
    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;
}*/
源文件, 语言: C++14

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 6
Accepted
time: 1ms
memory: 7604kb

input:

1

output:

1
1 1

result:

ok 1 queen(s)

Test #2:

score: 0
Accepted
time: 1ms
memory: 7700kb

input:

2

output:

1
1 1

result:

ok 1 queen(s)

Test #3:

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

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: 1ms
memory: 7664kb

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: -6
Wrong Answer
time: 1ms
memory: 7736kb

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 5
2 4
4 2
5 2
4 5
3 4
5 4
4 4
3 5
5 3
4 3
5 5

result:

wrong answer the cell (2, 5) is attacking by 5 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 繁體中文 简体中文

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