CSES - Datatähti 2017 loppu - Results
Submission details
Task:Ruudukko
Sender:ollpu
Submission time:2017-06-25 10:53:37 +0300
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED35
#2ACCEPTED21
#3ACCEPTED44
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1details
#2ACCEPTED0.03 s1details
#3ACCEPTED0.06 s1details
#4ACCEPTED0.05 s1details
#5ACCEPTED0.04 s1details
#6ACCEPTED0.04 s1details
#7ACCEPTED0.03 s1details
#8ACCEPTED0.04 s1details
#9ACCEPTED0.03 s1details
#10ACCEPTED0.03 s2details
#11ACCEPTED0.04 s2details
#12ACCEPTED0.04 s2details
#13ACCEPTED0.04 s2details
#14ACCEPTED0.04 s2details
#15ACCEPTED0.04 s2details
#16ACCEPTED0.03 s3details
#17ACCEPTED0.05 s3details
#18ACCEPTED0.03 s3details
#19ACCEPTED0.08 s3details
#20ACCEPTED0.13 s3details
#21ACCEPTED0.18 s3details

Code

#include <iostream>
#include <unordered_set>
using namespace std;
const int N = 1000;
int n;
int tc[N], t[N][N];
int tctmp[N];
int rrange(int a, int b) {
  if (b < a) return a;
  return rand()%(b-a+1)+a;
}
bool recover() {
  for (int j = 0; j < n; ++j) {
    tc[j] = tctmp[j];
  }
  return 1;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  if (n < 4) {
    cout << "QAQ\n";
    return 0;
  }
  unordered_set<long> rsa;
  while (true) {
    rsa.clear();
    bool f = 1;
    for (int i = 0; i < n; ++i) tc[i] = 0;
    for (int i = 0; i < n; ++i) {
      long rs, rstryc = 0;
      do {
        if (rstryc++ > 1000-i) {
          f = 0;
          break;
        }
        rs = 0;
        for (int j = 0; j < n; ++j) tctmp[j] = tc[j];
        for (int j = 0; j < i; ++j) rs += t[i][j];
        for (int j = i; j < n; ++j) {
          int o;
          do {
            o = rrange(1, n);
          } while (tc[o-1] == n);
          tc[o-1]++;
          t[i][j] = o;
          rs += o;
          // cout <<"--"<< j << endl;
        }
      } while (rsa.count(rs) && recover());
      if (!f) break;
      rsa.insert(rs);
      rstryc = 0;
      do {
        if (rstryc++ > 1000-i) {
          f = 0;
          break;
        }
        rs = 0;
        for (int j = 0; j < n; ++j) tctmp[j] = tc[j];
        for (int j = 0; j < i+1; ++j) rs += t[j][i];
        for (int j = i+1; j < n; ++j) {
          int o;
          do {
            o = rrange(1, n);
          } while (tc[o-1] == n);
          tc[o-1]++;
          t[j][i] = o;
          rs += o;
          // cout <<"--"<< j << endl;
        }
      } while (rsa.count(rs) && recover());
      if (!f) break;
      rsa.insert(rs);
    }
    // for (int i = 0; i < n; ++i) {
    //   for (int j = 0; j < n; ++j) {
    //     cout << t[i][j] << " ";
    //   }
    //   cout << "\n";
    // }
    if (!f) continue;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        cout << t[i][j] << " ";
      }
      cout << "\n";
    }
    break;
  }
}

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

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

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

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
8 4 1 5 5 2 1 5 
4 5 6 3 8 7 4 1 
3 7 1 2 1 8 5 1 
3 1 4 5 6 1 7 6 
2 5 2 4 7 5 8 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
8 5 4 7 2 1 4 1 8 
5 6 7 4 7 6 3 1 4 
3 5 2 1 8 1 1 2 2 
8 6 8 4 5 4 9 5 7 
3 8 4 8 6 6 3 9 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
10 2 1 9 3 9 9 8 7 7 
8 10 9 1 5 6 3 5 4 3 
3 4 2 2 10 10 10 9 2 4 
5 7 9 7 9 6 2 1 3 6 
9 4 1 6 7 7 8 7 1 10 
...

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
3 1 4 4 
3 3 3 4 
1 1 2 2 
1 2 2 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
22 15 26 12 15 4 19 24 5 4 8 2...

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
7 38 26 43 27 15 27 25 18 13 4...

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
14 4 17 33 37 76 37 79 16 24 1...

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
3 82 97 36 40 86 72 63 7 2 24 ...

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
3 1 4 4 
3 3 3 4 
1 1 2 2 
1 2 2 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
35 110 43 47 57 110 104 16 97 ...

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
150 231 260 256 398 346 199 11...

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
155 512 339 408 702 547 434 30...

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
429 522 324 775 822 161 971 53...