Task: | Summat |
Sender: | FooBat |
Submission time: | 2020-09-27 19:16:53 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 32 |
#3 | ACCEPTED | 56 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#5 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.01 s | 2, 3 | details |
#7 | ACCEPTED | 0.01 s | 2, 3 | details |
#8 | ACCEPTED | 0.01 s | 2, 3 | details |
#9 | ACCEPTED | 0.01 s | 2, 3 | details |
#10 | ACCEPTED | 0.01 s | 2, 3 | details |
#11 | ACCEPTED | 0.01 s | 3 | details |
#12 | ACCEPTED | 0.02 s | 3 | details |
#13 | ACCEPTED | 0.03 s | 3 | details |
#14 | ACCEPTED | 0.05 s | 3 | details |
#15 | ACCEPTED | 0.13 s | 3 | details |
Code
#include <iostream>#include <vector>#include <algorithm>void print(const std::vector<int>& vals){for (unsigned i = 0; i < vals.size(); i++){std::cout << vals[i];if (i < vals.size() - 1)std::cout << " ";}std::cout << "\n";}std::vector<int> pairs(const std::vector<int>& numbers){std::vector<int> results;for (unsigned i = 0; i < numbers.size() - 1; i++){for (unsigned j = i + 1; j < numbers.size(); j++){results.emplace_back(numbers[i] + numbers[j]);}}std::sort(results.begin(), results.end());return results;}int test(int idx, int value, const std::vector<int>& numbers, std::vector<bool>& used){for (unsigned i = idx; i < numbers.size(); i++){if (used[i])continue;if (value < numbers[i])return 0;if (value == numbers[i]){return i;}}return 0;}std::vector<int> solve(unsigned n, const std::vector<int>& numbers){std::vector<bool> used;used.resize(numbers.size());std::vector<int> solved;solved.resize(numbers.size());int min_unused = 2;int a_max = numbers[0];std::vector<int> tests;auto testAndMark = [&](int idx, int value) -> bool{for (unsigned i = 1; i < solved.size(); i++){int val = solved[i] + value;int foundIdx = test(min_unused, val, numbers, used);if (!foundIdx){for (int f : tests)used[f] = false;return false;break;}used[foundIdx] = true;tests.emplace_back(foundIdx);}return true;};auto testFirst = [&](int b, int c){int val = b + c;for (unsigned i = 1; i < numbers.size(); i++){if (val < numbers[i])return false;if (val == numbers[i]){return true;}}return false;};for (int a = 1; a < a_max; a++){int b = numbers[0] - a;int next = numbers[1] - a;if (!testFirst(b, next)){continue;}solved.clear();solved.emplace_back(a);solved.emplace_back(b);used.clear();used.resize(numbers.size());min_unused = 2;tests.clear();if (!testAndMark(min_unused, next)){continue;}solved.emplace_back(next);while (solved.size() < n){for (unsigned i = min_unused; i < numbers.size(); i++){if (!used[i]){min_unused = i;break;}}next = numbers[min_unused] - a;used[min_unused++] = true;tests.clear();if (!testAndMark(min_unused, next)){break;}solved.emplace_back(next);}if (solved.size() == n)break;}return solved;}std::vector<int> readInput(unsigned& n){std::vector<int> inputs;std::cin >> n;unsigned reads = (n*(n - 1)) / 2;for (unsigned i = 0; i < reads; i++){int v;std::cin >> v;inputs.emplace_back(v);}return inputs;}std::vector<int> testInputs(unsigned &n){std::vector<int> test = { 134123123,26365345,31231231,123123123, 123120000,123125151 };std::sort(test.begin(), test.end());n = test.size();print(test);auto vec = pairs(test);print(vec);return vec;}int main(){unsigned n;std::vector<int> vec = readInput(n);//std::vector<int> vec = testInputs(n);std::sort(vec.begin(), vec.end());print(solve(n, vec));}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
5 2 2 2 2 2 2 2 2 2 2 |
correct output |
---|
1 1 1 1 1 |
user output |
---|
1 1 1 1 1 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
5 3 4 5 5 6 6 7 7 8 9 |
correct output |
---|
1 2 3 4 5 |
user output |
---|
1 2 3 4 5 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
5 5 6 6 6 9 9 9 10 10 10 |
correct output |
---|
1 4 5 5 5 |
user output |
---|
1 4 5 5 5 |
Test 4
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
5 2 3 3 6 6 6 6 7 7 10 |
correct output |
---|
1 1 2 5 5 |
user output |
---|
1 1 2 5 5 |
Test 5
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
5 4 5 5 5 5 6 6 6 7 7 |
correct output |
---|
2 2 3 3 4 |
user output |
---|
2 2 3 3 4 |
Test 6
Group: 2, 3
Verdict: ACCEPTED
input |
---|
20 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
Test 7
Group: 2, 3
Verdict: ACCEPTED
input |
---|
20 3 4 5 5 6 6 7 7 7 8 8 8 9 9 9 ... |
correct output |
---|
1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
Test 8
Group: 2, 3
Verdict: ACCEPTED
input |
---|
20 52 55 55 57 62 62 63 64 66 71 ... |
correct output |
---|
1 51 54 54 56 61 61 62 63 65 7... |
user output |
---|
1 51 54 54 56 61 61 62 63 65 7... |
Test 9
Group: 2, 3
Verdict: ACCEPTED
input |
---|
20 25 30 31 32 36 39 40 41 45 45 ... |
correct output |
---|
8 17 22 23 24 28 43 50 53 55 6... |
user output |
---|
8 17 22 23 24 28 43 50 53 55 6... |
Test 10
Group: 2, 3
Verdict: ACCEPTED
input |
---|
20 9 10 14 17 17 20 21 22 24 25 2... |
correct output |
---|
1 8 9 13 16 19 30 32 38 40 43 ... |
user output |
---|
1 8 9 13 16 19 30 32 38 40 43 ... |
Test 11
Group: 3
Verdict: ACCEPTED
input |
---|
100 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... Truncated |
Test 12
Group: 3
Verdict: ACCEPTED
input |
---|
100 3 4 5 5 6 6 7 7 7 8 8 8 9 9 9 ... |
correct output |
---|
1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
1 2 3 4 5 6 7 8 9 10 11 12 13 ... Truncated |
Test 13
Group: 3
Verdict: ACCEPTED
input |
---|
100 502824619 505239810 505668108 ... |
correct output |
---|
1 502824618 505239809 50566810... |
user output |
---|
1 502824618 505239809 50566810... Truncated |
Test 14
Group: 3
Verdict: ACCEPTED
input |
---|
100 17871832 41618648 51611938 538... |
correct output |
---|
3939271 13932561 37679377 4989... |
user output |
---|
3939271 13932561 37679377 4989... Truncated |
Test 15
Group: 3
Verdict: ACCEPTED
input |
---|
100 70588435 115481965 116040218 1... |
correct output |
---|
5902586 64685849 109579379 110... |
user output |
---|
5902586 64685849 109579379 110... Truncated |