CSES - Datatähti Open 2021 - Results
Submission details
Task:Split in Three
Sender:apostoldaniel854
Submission time:2021-01-29 23:31:45 +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>

using namespace std;

using ll = long long;

const int MAX_N = 100, MAX_K = 2000;
int sum[3];
int sol[1 + MAX_N];

namespace brut {
    using ll = long long;
    const int MAX_N = 100;
    int p3[1 + MAX_N];

    int main (int n) {
        int rest = n % 6;
        if (rest < 6)
            rest += 6;
        rest = min (rest, n);
        p3[0] = 1;
        for (int i = 1; i <= rest; i++)
            p3[i] = p3[i - 1] * 3;
        vector <int> values (n + 1);
        for (int i = n; i > rest; i--) {
            int bucket = 2 - (n - i) % 3;
            int inv = ((n - i) / 3) & 1;
            if (inv)
                bucket = 2 - bucket;
            values[i] = bucket + 1;
        }
        for (int mask = 0; mask < p3[rest]; mask++) {
            vector <int> sum (3, 0);
            for (int pos = 0; pos < rest; pos++) {
                int bucket = (mask / p3[pos]) % 3;
                sum[bucket] += pos + 1;
                values[pos + 1] = bucket + 1;
            }
            if (sum[0]  + 1 == sum[1] && sum[1] + 1 == sum[2]) {
                for (int i = 1; i <= n; i++)
                    cout << values[i] << " ";
                cout << "\n";
                return 1;
            }
        }
        cout << "IMPOSSIBLE\n";
        return 0;
    }
}

int main () {
    int n;
    cin >> n;
    brut::main (n);
    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 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 2 3 3 2 1 3 2 1 1 2 3 3 2 1 ...

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

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

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

Test 15

Group: 2

Verdict: ACCEPTED

input
100

correct output
IMPOSSIBLE

user output
IMPOSSIBLE