CSES - Datatähti Open 2017 - Results
Submission details
Task:Grid
Sender:abcdef6199
Submission time:2017-01-22 12:40:42 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED35
#2ACCEPTED21
#3ACCEPTED44
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1details
#2ACCEPTED0.03 s1details
#3ACCEPTED0.03 s1details
#4ACCEPTED0.04 s1details
#5ACCEPTED0.04 s1details
#6ACCEPTED0.04 s1details
#7ACCEPTED0.06 s1details
#8ACCEPTED0.04 s1details
#9ACCEPTED0.04 s1details
#10ACCEPTED0.04 s2details
#11ACCEPTED0.04 s2details
#12ACCEPTED0.03 s2details
#13ACCEPTED0.05 s2details
#14ACCEPTED0.04 s2details
#15ACCEPTED0.04 s2details
#16ACCEPTED0.04 s3details
#17ACCEPTED0.03 s3details
#18ACCEPTED0.06 s3details
#19ACCEPTED0.06 s3details
#20ACCEPTED0.10 s3details
#21ACCEPTED0.13 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:58:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^

Code

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

typedef long long LL;
typedef pair<int, int> II;

const int N = (int) 1e3 + 10;
int n, a[N][N], r[N], c[N];
bool fre[N]; int cnt[N];
bool fre2[N];
int timer;

bool Check() {
    bool ans = true;
    for (int i = 1; i <= n; ++i) {
        if (fre[c[i]] == false || fre2[c[i]] == false) ans = false;
        fre2[c[i]] = false;
    }
    for (int i = 1; i <= n; ++i) fre2[c[i]] = true;
    return ans;
}

void Attemp(int x, int y) {
    if (x == n + 1) {
        if (Check()) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) cout << a[i][j] << " ";
                cout << endl;
            }
            if (++timer == 1) exit(0);
            cout << endl;
        }
        return;
    }
    for (int v = 1; v <= n; ++v) if (cnt[v] < n) {
        r[x] += v;
        c[y] += v;
        cnt[v]++; a[x][y] = v;
        if (y < n) Attemp(x, y + 1); else {
            if (fre[r[x]]) {
                fre[r[x]] = false;
                Attemp(x + 1, 1);
                fre[r[x]] = true;
            }
        }
        cnt[v]--;
        r[x] -= v;
        c[y] -= v;
    }
}

int main() {
    #ifdef LOCAL
        freopen("Data.inp", "r", stdin);
        freopen("Data.out", "w", stdout);
    #endif

    scanf("%d", &n);

    if (n <= 10) {
        memset(fre, true, sizeof fre);
        memset(fre2, true, sizeof fre2);
        memset(cnt, 0, sizeof cnt);
        fre[r[1] = n * (n + 1) / 2] = false;
        for (int i = 1; i <= n; ++i) cnt[i]++, a[1][i] = i, c[i] = i;
        Attemp(2, 1);
        puts("QAQ");
    }
    else {
        for (int i = 1; i <= n; ++i) a[1][i] = i;
        for (int v = 1, x = 2, y = 1; v <= n; ++v) {
            for (int t = 1; t <= n - 1; ++t) {
                a[x][y] = v;
                y++; if (y == n + 1) x++, y = 1;
            }
        }
        if (n % 2 == 0) {
            swap(a[n][n], a[n - 1][n / 2 + 1]);
            swap(a[n / 2 + 1][n], a[n / 2 + 2][n / 2]);
        }
        else {
            if (n % 4 == 1) {
                swap(a[n][1], a[n][(n + 1) / 2]);
            }
            else {
                a[n - 1][n - 1] = a[n - 1][n] = n;
                a[n][(n + 1) / 2] = n - 1;
                a[n][1] = n;
                a[n][(n + 1) / 4] = a[n][(n + 1) / 2 + (n + 1) / 4] = n - 1;
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) printf("%d ", a[i][j]);
            puts("");
        }
    }
    return 0;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
2

correct output
QAQ

user output
QAQ

Test 2

Group: 1

Verdict: ACCEPTED

input
3

correct output
QAQ

user output
QAQ

Test 3

Group: 1

Verdict: ACCEPTED

input
4

correct output
3 4 3 4
3 1 1 2
4 4 3 2
2 2 1 1

user output
1 2 3 4 
1 1 1 2 
2 2 4 3 
3 3 4 4 

Test 4

Group: 1

Verdict: ACCEPTED

input
5

correct output
2 3 4 1 1 
3 4 2 1 2 
4 2 3 1 3 
4 3 2 1 4 
5 5 5 5 5 

user output
1 2 3 4 5 
1 1 1 1 2 
2 2 2 3 3 
3 3 4 4 5 
4 5 4 5 5 

Test 5

Group: 1

Verdict: ACCEPTED

input
6

correct output
2 3 4 5 1 1 
3 4 5 2 1 2 
4 5 2 3 1 3 
5 2 3 4 1 4 
5 4 3 2 1 5 
...

user output
1 2 3 4 5 6 
1 1 1 1 1 2 
2 2 2 2 3 3 
3 3 3 4 4 5 
4 4 4 6 5 5 
...

Test 6

Group: 1

Verdict: ACCEPTED

input
7

correct output
2 3 4 5 6 1 1 
3 4 5 6 2 1 2 
4 5 6 2 3 1 3 
5 6 2 3 4 1 4 
6 2 3 4 5 1 5 
...

user output
1 2 3 4 5 6 7 
1 1 1 1 1 1 2 
2 2 2 2 2 3 3 
3 3 3 3 4 4 4 
4 4 4 5 5 5 5 
...

Test 7

Group: 1

Verdict: ACCEPTED

input
8

correct output
2 3 4 5 6 7 1 1 
3 4 5 6 7 2 1 2 
4 5 6 7 2 3 1 3 
5 6 7 2 3 4 1 4 
6 7 2 3 4 5 1 5 
...

user output
1 2 3 4 5 6 7 8 
1 1 1 1 1 1 1 2 
2 2 2 2 2 2 3 3 
3 3 3 3 3 4 4 4 
4 4 4 4 5 5 5 6 
...

Test 8

Group: 1

Verdict: ACCEPTED

input
9

correct output
2 3 4 5 6 7 8 1 1 
3 4 5 6 7 8 2 1 2 
4 5 6 7 8 2 3 1 3 
5 6 7 8 2 3 4 1 4 
6 7 8 2 3 4 5 1 5 
...

user output
1 2 3 4 5 6 7 8 9 
1 1 1 1 1 1 1 1 2 
2 2 2 2 2 2 2 3 3 
3 3 3 3 3 3 4 4 4 
4 4 4 4 4 5 5 5 5 
...

Test 9

Group: 1

Verdict: ACCEPTED

input
10

correct output
2 3 4 5 6 7 8 9 1 1 
3 4 5 6 7 8 9 2 1 2 
4 5 6 7 8 9 2 3 1 3 
5 6 7 8 9 2 3 4 1 4 
6 7 8 9 2 3 4 5 1 5 
...

user output
1 2 3 4 5 6 7 8 9 10 
1 1 1 1 1 1 1 1 1 2 
2 2 2 2 2 2 2 2 3 3 
3 3 3 3 3 3 3 4 4 4 
4 4 4 4 4 4 5 5 5 5 
...

Test 10

Group: 2

Verdict: ACCEPTED

input
3

correct output
QAQ

user output
QAQ

Test 11

Group: 2

Verdict: ACCEPTED

input
4

correct output
3 4 3 4
3 1 1 2
4 4 3 2
2 2 1 1

user output
1 2 3 4 
1 1 1 2 
2 2 4 3 
3 3 4 4 

Test 12

Group: 2

Verdict: ACCEPTED

input
29

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...

user output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

Test 13

Group: 2

Verdict: ACCEPTED

input
48

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...

user output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

Test 14

Group: 2

Verdict: ACCEPTED

input
80

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...

user output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

Test 15

Group: 2

Verdict: ACCEPTED

input
97

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...

user output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

Test 16

Group: 3

Verdict: ACCEPTED

input
3

correct output
QAQ

user output
QAQ

Test 17

Group: 3

Verdict: ACCEPTED

input
4

correct output
3 4 3 4
3 1 1 2
4 4 3 2
2 2 1 1

user output
1 2 3 4 
1 1 1 2 
2 2 4 3 
3 3 4 4 

Test 18

Group: 3

Verdict: ACCEPTED

input
111

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...

user output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

Test 19

Group: 3

Verdict: ACCEPTED

input
506

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...

user output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

Test 20

Group: 3

Verdict: ACCEPTED

input
844

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...

user output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

Test 21

Group: 3

Verdict: ACCEPTED

input
991

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...

user output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...