CSES - Datatähti Open 2021 - Results
Submission details
Task:Split in Three
Sender:NewResolution
Submission time:2021-01-30 06:24:01 +0200
Language:C++ (C++17)
Status:COMPILE ERROR

Compiler report

output/ccaeXNz1.o: In function `_GLOBAL__sub_I_dp':
code.cpp:(.text.startup+0x323): relocation truncated to fit: R_X86_64_PC32 against `.bss'
code.cpp:(.text.startup+0x341): relocation truncated to fit: R_X86_64_PC32 against `.bss'
collect2: error: ld returned 1 exit status

Code

#include <iostream>

using namespace std;

int dp[101][5051][5051];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int m = n * (n + 1) / 2;
    dp[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= m; k++) {
                if (dp[i - 1][j][k]) dp[i][j][k] = 3;
                else if (j >= i && dp[i - 1][j - i][k]) dp[i][j][k] = 1;
                else if (k >= i && dp[i - 1][j][k - i]) dp[i][j][k] = 2;
            }
        }
    }
    if (m % 3 != 0 || !dp[n][m / 3 - 1][m / 3]) cout << "IMPOSSIBLE";
    else {
        int j = m / 3 - 1, k = m / 3;
        int ans[n];
        for (int i = n; i > 0; i--) {
            ans[i - 1] = dp[i][j][k];
            if (ans[i - 1] == 1) j -= i;
            else if (ans[i - 1] == 2) k -= i;
        }
        for (int i = 0; i < n; i++) cout << ans[i] << " ";
    }
    return 0;
}