CSES - Datatähti Open 2021 - Results
Submission details
Task:Split in Three
Sender:decpero
Submission time:2021-01-30 20:34:49 +0200
Language:C++11
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED22
#2ACCEPTED78
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#2ACCEPTED0.01 s1, 2details
#3ACCEPTED0.01 s1, 2details
#4ACCEPTED0.01 s1, 2details
#5ACCEPTED0.01 s1, 2details
#6ACCEPTED0.01 s1, 2details
#7ACCEPTED0.01 s1, 2details
#8ACCEPTED0.01 s1, 2details
#9ACCEPTED0.02 s2details
#10ACCEPTED0.46 s2details
#11ACCEPTED0.49 s2details
#12ACCEPTED0.01 s2details
#13ACCEPTED0.54 s2details
#14ACCEPTED0.56 s2details
#15ACCEPTED0.01 s2details

Code

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define ppb pop_back
#define x first
#define y second
#define int long long
#define mp make_pair

using namespace std;

const int inf = 1e18, sz = 4105;

int ans[sz];

int used[sz][sz];

signed main (){
//    cin.tie(0);
//    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    int d = (n*(n+1))/2;
    if (d % 3 != 0) cout << "IMPOSSIBLE";
    else {
         d /= 3;
         used[0][0] = -1;
         for (int i = 1; i <= n; ++i){
             for (int j = d+5; j >= 0; --j){
                for (int z = d+5; z >= 0; --z){
                    if (used[j][z] == 0){
                        if (j >= i && used[j - i][z]) used[j][z] = i;
                        else if (z >= i && used[j][z - i]) used[j][z] = -i;
                    }
                    }
            }
        }
//        cout << "norm" << '\n';
        int x = d - 1, y = d;
        while (x != 0 || y != 0){
            if (used[x][y] > 0) {
                ans[used[x][y]] = 1;
                x -= used[x][y];
            }
            else {
                ans[abs(used[x][y])] = 2;
                y -= abs(used[x][y]);
            }
        }
        for (int i = 1; i <= n; ++i){
            if (ans[i] != 0) cout << ans[i] << ' ';
            else cout << 3 << ' ';
        }
    }
    return 0;
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
3

correct output
1 2 3 

user output
1 2 3 

Test 2

Group: 1, 2

Verdict: ACCEPTED

input
4

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 3

Group: 1, 2

Verdict: ACCEPTED

input
5

correct output
1 3 1 3 2 

user output
3 2 2 1 3 

Test 4

Group: 1, 2

Verdict: ACCEPTED

input
6

correct output
1 3 2 2 1 3 

user output
1 3 2 2 1 3 

Test 5

Group: 1, 2

Verdict: ACCEPTED

input
7

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 6

Group: 1, 2

Verdict: ACCEPTED

input
8

correct output
2 3 1 2 3 3 2 1 

user output
2 2 2 1 3 2 1 3 

Test 7

Group: 1, 2

Verdict: ACCEPTED

input
9

correct output
1 2 3 1 2 3 3 2 1 

user output
2 2 2 2 2 1 3 1 3 

Test 8

Group: 1, 2

Verdict: ACCEPTED

input
10

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 9

Group: 2

Verdict: ACCEPTED

input
42

correct output
1 3 2 2 1 3 1 2 3 3 2 1 1 2 3 ...

user output
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

Test 10

Group: 2

Verdict: ACCEPTED

input
95

correct output
1 3 1 3 2 1 2 3 3 2 1 1 2 3 3 ...

user output
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

Test 11

Group: 2

Verdict: ACCEPTED

input
96

correct output
1 3 2 2 1 3 1 2 3 3 2 1 1 2 3 ...

user output
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

Test 12

Group: 2

Verdict: ACCEPTED

input
97

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 13

Group: 2

Verdict: ACCEPTED

input
98

correct output
2 3 1 2 3 3 2 1 1 2 3 3 2 1 1 ...

user output
2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 ...

Test 14

Group: 2

Verdict: ACCEPTED

input
99

correct output
1 2 3 1 2 3 3 2 1 1 2 3 3 2 1 ...

user output
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

Test 15

Group: 2

Verdict: ACCEPTED

input
100

correct output
IMPOSSIBLE

user output
IMPOSSIBLE