CSES - Datatähti Open 2021 - Results
Submission details
Task:Split in Three
Sender:voventa
Submission time:2021-01-31 13:47:08 +0200
Language:C++17
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.01 s2details
#10ACCEPTED0.01 s2details
#11ACCEPTED0.01 s2details
#12ACCEPTED0.01 s2details
#13ACCEPTED0.01 s2details
#14ACCEPTED0.01 s2details
#15ACCEPTED0.01 s2details

Code

#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(a) (int)a.size()
#define pb push_back
#define int unsigned long long

using namespace std;
typedef long long ll;

void solve();

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
    return 0;
}

bitset <6000> b[110];

int used[110];

void solve() {
    int n;
    cin >> n;
    if ((n * (n + 1) / 2) % 3 != 0) {
        cout << "IMPOSSIBLE\n";
        return;
    }
    b[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        b[i] = (b[i - 1] | (b[i - 1] << i));
        used[i] = 3;
    }
    int x = (n * (n + 1) / 2 - 3) / 3;
    if (!b[n][x]) {
        cout << "IMPOSSIBLE\n";
        return;
    }
    for (int i = n; i > 0; --i) {
        if (x >= i && b[i - 1][x - i]) {
            used[i] = 1;
            x -= i;
        }
    }
    x = (n * (n + 1) / 2 - 3) / 3 + 1;
    if (!b[n][x]) {
        cout << "IMPOSSIBLE\n";
        return;
    }
    for (int i = n; i > 0; --i) {
        if (used[i] == 1)
            continue;
        if (x >= i && b[i - 1][x - i]) {
            used[i] = 2;
            x -= i;
        }
    }
    if (x != 0) {
        cout << "IMPOSSIBLE\n";
        return;
    }
    for (int i = 1; i <= n; ++i) {
        cout << used[i] << " ";
    }
    return;
}

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

Test 4

Group: 1, 2

Verdict: ACCEPTED

input
6

correct output
1 3 2 2 1 3 

user output
3 2 3 3 2 1 

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

Test 7

Group: 1, 2

Verdict: ACCEPTED

input
9

correct output
1 2 3 1 2 3 3 2 1 

user output
3 3 3 3 1 3 2 2 1 

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
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...

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
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...

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
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...

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
3 3 3 3 1 3 3 3 3 3 3 3 3 3 3 ...

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
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...

Test 15

Group: 2

Verdict: ACCEPTED

input
100

correct output
IMPOSSIBLE

user output
IMPOSSIBLE