Task: | Split in Three |
Sender: | lookcook |
Submission time: | 2021-01-30 17:31:23 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 22 |
#2 | ACCEPTED | 78 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2 | details |
#2 | ACCEPTED | 0.01 s | 1, 2 | details |
#3 | ACCEPTED | 0.01 s | 1, 2 | details |
#4 | ACCEPTED | 0.01 s | 1, 2 | details |
#5 | ACCEPTED | 0.01 s | 1, 2 | details |
#6 | ACCEPTED | 0.01 s | 1, 2 | details |
#7 | ACCEPTED | 0.01 s | 1, 2 | details |
#8 | ACCEPTED | 0.01 s | 1, 2 | details |
#9 | ACCEPTED | 0.01 s | 2 | details |
#10 | ACCEPTED | 0.01 s | 2 | details |
#11 | ACCEPTED | 0.01 s | 2 | details |
#12 | ACCEPTED | 0.01 s | 2 | details |
#13 | ACCEPTED | 0.01 s | 2 | details |
#14 | ACCEPTED | 0.01 s | 2 | details |
#15 | ACCEPTED | 0.01 s | 2 | details |
Compiler report
input/code.cpp: In function 'long long int rec(long long int, long long int)': input/code.cpp:13:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (pos == v.size()) { ~~~~^~~~~~~~~~~ input/code.cpp: In function 'int main()': input/code.cpp:51:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] while (p != v.size()) { ~~^~~~~~~~~~~ input/code.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] while (p != v.size()) { ~~^~~~~~~~~~~ input/code.cpp:83:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] while (p != v.size()) { ~~^~~~~~~~~~~
Code
#include <bits/stdc++.h>#define int long longusing namespace std;int dp[105][5055];int to[105][5055];int n;vector<int> v;int seek;int rec(int pos, int sum) {if (pos == v.size()) {if (sum == seek) return true;else return false;}if (dp[pos][sum] != -1) return dp[pos][sum];int res = 0;if (rec(pos+1,sum) == 1) {res = 1;to[pos][sum] = 0;} else if (rec(pos+1,sum+v[pos]) == 1) {res = 1;to[pos][sum] = 1;}dp[pos][sum] = res;return res;}signed main() {ios_base::sync_with_stdio(0);cin.tie(0);cin >> n;int taken[n + 1];for (int i = 0; i <= n; i++) taken[i] = 0;int sum = (n * (n + 1)) / 2;if (sum%3 != 0) {cout << "IMPOSSIBLE\n";//exit(0);} else {//cout << "Sum = " << sum << '\n';int aSum = (sum) / 3 - 1;int bSum = (sum) / 3;int cSum = (sum) / 3 + 1;for (int i = 1; i <= n; i++) v.push_back(i);for (int i = 0; i < 105; i++) for (int j = 0; j < 5055; j++) dp[i][j] = -1;seek = aSum;rec(0, 0);int p = 0;int s = 0;while (p != v.size()) {if (to[p][s] == 0) {p++;} else if (to[p][s] == 1) {s += v[p];taken[v[p]] = 1;p++;}}v = {};for (int i = 1; i <= n; i++) if (taken[i] == 0) v.push_back(i);for (int i = 0; i < 105; i++) for (int j = 0; j < 5055; j++) dp[i][j] = -1;seek = bSum;rec(0, 0);p = 0;s = 0;while (p != v.size()) {if (to[p][s] == 0) {p++;} else if (to[p][s] == 1) {s += v[p];taken[v[p]] = 2;p++;}}v = {};for (int i = 1; i <= n; i++) if (taken[i] == 0) v.push_back(i);for (int i = 0; i < 105; i++) for (int j = 0; j < 5055; j++) dp[i][j] = -1;seek = cSum;rec(0, 0);p = 0;s = 0;while (p != v.size()) {if (to[p][s] == 0) {p++;} else if (to[p][s] == 1) {s += v[p];taken[v[p]] = 3;p++;}}for (int i = 1; i <= n; i++) cout << taken[i] << ' ';cout << '\n';int a = 0, b = 0, c = 0;for (int i = 1; i <= n; i++) {if (taken[i] == 1) a += i;if (taken[i] == 2) b += i;if (taken[i] == 3) c += i;}}}/**/
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 3 2 2 3 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 3 2 1 1 3 2 |
Test 7
Group: 1, 2
Verdict: ACCEPTED
input |
---|
9 |
correct output |
---|
1 2 3 1 2 3 3 2 1 |
user output |
---|
3 3 2 3 2 1 2 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 |
---|
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 ... Truncated |
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 ... Truncated |
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 3 3 3 3 3 3 3 3 3 3 3 ... Truncated |
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 ... Truncated |
Test 15
Group: 2
Verdict: ACCEPTED
input |
---|
100 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |