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

Code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const ll mod7 = 1000000007;

#define eb(x) emplace_back(x)
#define ef(x) emplace_front(x)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define ob(x) pop_back(x)
#define of(x) pop_front(x)
#define mp(a, b) make_pair(a, b)

#define power(x, p) round(pow(x, (double)p))
#define all(x) x.begin(), x.end()
#define sortAs(x) sort(all(x));
#define sortDes(x) sort(all(x), std::greater<ll>());

#define fori(x) for (ll i = 0; i < x; i++)
#define forj(x) for (ll j = 0; j < x; j++)
#define fork(x) for (ll k = 0; k < x; k++)

#define ret(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define rep(u, s, x) for (ll u = s; u <= x; u++)
#define rem(u, x, s) for (ll u = s; u >= x; u--)

#define RET(t) cout << t << endl; return 0;
#define RETIF(i, t) if (i) { cout << t << endl; return 0; }
#define BREAKIF(i, t) if (i) { cout << t << endl; break; }
#define CONTIF(i, t) if (i) { cout << t << endl; continue; }

#define NEWLINE cout << endl;
#define DBG(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); cout << endl; }

vector<string> split(const string& s, char c) {
	vector<string> v;
	stringstream ss(s);
	string x;
	while (getline(ss, x, c))
		v.emplace_back(x);
	return move(v);
}

void err(vector<string>::iterator it) {}
template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
	cout << it -> substr((*it)[0] == ' ', it -> length()) << ": " << a << " ";
	err(++it, args...);
}

#define DBGARRAY(x, s) cout << #x << ": "; for (int z = 0; z < s; z++) cout << x[z] << " "; cout << endl;
#define DBGVECTOR(x) cout << #x << ": "; for (ll z = 0; z < x.size(); z++) cout << x[z] << " "; cout << endl;
#define DBGVECTORPAR(x, p) cout << #x << ": "; for (ll z = 0; z < x.size(); z++) cout << x[z].p << " "; cout << endl;
#define DBGMAP(x) cout << #x << ":" << endl; for (auto z = x.begin(); z != x.end(); z++) { cout << z->first << ": " << z->second << endl; }
#define DBGSET(x) cout << #x << ":" << endl; for (auto z = x.begin(); z != x.end(); z++) { cout << *z << endl;}

bool isPrime(long long a) { if (a <= 1) return 0; for(long long i = 2; i * i <= a; i++) { if(a % i == 0) return 0; } return 1; }

ll lcm(ll a, ll b) { return __gcd(a, b) ? (a / __gcd(a, b) * b) : 0; }

template<typename T>
ll biggest(T x) {ll b_i = 0; fori(x.size()) {if (x[b_i] < x[i]) {b_i = i;} } return b_i;}
template<typename T>
ll smallest(T x) {ll s_i = 0; fori(x.size()) {if (x[s_i] > x[i]) {s_i = i;} } return s_i;}

template<typename T>
string tostring(T num) { stringstream convert; convert << num; return convert.str(); }
template<typename T>
ll tonumber(T stringNum) { ll a; stringstream convert; convert << stringNum; convert >> a; return a; }


ll A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z;
char C1, C2, C3, C4;
string S1, S2, S3, S4;
vl V1, V2, V3, V4;
bool B1, B2;

int field[1001][1001];

pair<int, int> one, two;

bool isOk()
{
    unordered_set<int> sums;

    int a = 0;

    fori(N)
    {
        int s = 0;
        forj(N)
        {
            s += field[i][j];
        }
        if (sums.count(s))
        {
            B1 ? one = mp(i, rand() % N) : two = mp(i, rand() % N);
            B1 = !B1;
            a++;
            if (a == 2)
                return false;
        }
        else
            sums.insert(s);
    }
    fori(N)
    {
        int s = 0;
        forj(N)
        {
            s += field[j][i];
        }
        if (sums.count(s))
        {
            B1 ? one = mp(rand() % N, i) : two = mp(rand() % N, i);
            B1 = !B1;
            a++;
            if (a == 2)
                return false;
        }
        else
            sums.insert(s);
    }
    if (a > 0)
        return false;
    return true;
}

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

    cin >> N;

    RETIF (N <= 3, "QAQ");

    fori(N)
    {
        forj(N)
        {
            field[i][j] = j + 1;
        }
    }

    fori(N)
    {
        random_shuffle(field[i], field[i] + N);
    }

    srand(time(0));

    while (true)
    {
        one = mp(rand() % N, rand() % N);
        two = mp(rand() % N, rand() % N);

        if (isOk())
        {
            fori(N)
            {
                forj(N)
                {
                    cout << field[i][j] << " ";
                }
                cout << endl;
            }
            return 0;
        }
        swap(field[one.first][one.second], field[two.first][two.second]);
    }
}

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

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

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

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

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

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

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

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 4 1 3 
3 3 1 1 
2 2 1 2 
4 4 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
5 5 12 5 25 17 18 2 27 10 4 23...

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
5 29 12 16 25 36 18 37 47 47 3...

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
5 52 12 70 25 36 18 37 27 51 6...

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
93 52 12 70 25 36 18 37 27 51 ...

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

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
111 52 12 70 25 36 18 110 27 1...

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
111 291 12 70 210 469 18 294 1...

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
111 291 702 70 561 469 707 294...

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
111 291 702 70 561 469 707 897...