Task: | Omenat |
Sender: | |
Submission time: | 2015-12-20 16:41:43 +0200 |
Language: | C++ |
Status: | READY |
Result: | 69 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 68.6 |
test | verdict | time | score | |
---|---|---|---|---|
#1 | ACCEPTED | 0.69 s | 7.6 | details |
#2 | ACCEPTED | 0.68 s | 6.4 | details |
#3 | ACCEPTED | 0.71 s | 7 | details |
#4 | ACCEPTED | 0.69 s | 6.1 | details |
#5 | ACCEPTED | 0.67 s | 6.8 | details |
#6 | ACCEPTED | 0.67 s | 6.2 | details |
#7 | ACCEPTED | 0.68 s | 7.8 | details |
#8 | ACCEPTED | 0.68 s | 6.6 | details |
#9 | ACCEPTED | 0.68 s | 7.3 | details |
#10 | ACCEPTED | 0.67 s | 6.8 | details |
Code
#include <iostream>#include <vector>#include <algorithm>#include <utility>#include <set>#include <sstream>typedef long long LL;using namespace std;int main(){srand(time(0));LL n; cin >> n;vector<LL> v;LL all = 0;for(int i = 0; i < n; i++){LL x; cin >> x;all += x;v.push_back(x);}LL target = all/2;set<LL> solution;LL sum = 0;for(int i = 0; i < n/2; i++){solution.insert(i);sum += v[i];}LL rounds = 8 * 1e6;LL best = 1e15;set<LL> best_solution = solution;for(int rep = 0; rep <= rounds; rep++){LL k = rand() % n;if(solution.count(k)){if(abs(target - (sum - v[k])) < abs(target - sum) || rand()%100 < 10){solution.erase(k);sum -= v[k];}} else{if(abs(target - (sum -+v[k])) < abs(target - sum) || rand()%100 < 10){solution.insert(k);sum += v[k];}}if(abs(sum - target) < best){best = abs(sum - target);best_solution = solution;}}for(int i = 0; i < n; i++){if(best_solution.count(i)) cout << "1 ";else cout << "2 ";}cout << endl;}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
95 779724552 231968220 985023789 ... |
correct output |
---|
(empty) |
user output |
---|
1 2 2 2 2 2 2 2 2 2 1 2 1 2 1 ... |
Test 2
Verdict: ACCEPTED
input |
---|
85 229722261 51722691 862338862 8... |
correct output |
---|
(empty) |
user output |
---|
2 2 2 1 1 2 2 2 1 2 2 2 2 2 1 ... |
Test 3
Verdict: ACCEPTED
input |
---|
97 398995377 989444445 634573915 ... |
correct output |
---|
(empty) |
user output |
---|
2 2 2 1 2 2 1 2 2 1 1 1 2 2 2 ... |
Test 4
Verdict: ACCEPTED
input |
---|
99 843687873 164010938 51269970 4... |
correct output |
---|
(empty) |
user output |
---|
2 1 2 1 2 2 1 1 2 2 1 2 2 1 1 ... |
Test 5
Verdict: ACCEPTED
input |
---|
90 864611617 418460939 773297829 ... |
correct output |
---|
(empty) |
user output |
---|
2 2 1 1 1 2 2 1 1 2 1 1 2 1 1 ... |
Test 6
Verdict: ACCEPTED
input |
---|
92 289890246 25801423 763027596 7... |
correct output |
---|
(empty) |
user output |
---|
1 2 1 1 1 1 1 1 1 1 2 1 1 1 2 ... |
Test 7
Verdict: ACCEPTED
input |
---|
89 879039800 50522278 850785072 4... |
correct output |
---|
(empty) |
user output |
---|
1 2 2 2 2 1 2 1 2 1 1 2 2 1 2 ... |
Test 8
Verdict: ACCEPTED
input |
---|
96 27192469 222283781 681532515 1... |
correct output |
---|
(empty) |
user output |
---|
2 2 2 1 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 9
Verdict: ACCEPTED
input |
---|
100 186459081 254674429 394007236 ... |
correct output |
---|
(empty) |
user output |
---|
1 2 2 1 2 1 2 2 2 1 2 2 1 1 1 ... |
Test 10
Verdict: ACCEPTED
input |
---|
98 612168861 979831717 671087051 ... |
correct output |
---|
(empty) |
user output |
---|
2 1 2 1 1 1 1 1 2 1 1 2 1 2 2 ... |