Task: | Omenat |
Sender: | |
Submission time: | 2015-12-20 16:44:56 +0200 |
Language: | C++ |
Status: | READY |
Result: | 86 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 85.5 |
test | verdict | time | score | |
---|---|---|---|---|
#1 | ACCEPTED | 0.94 s | 10 | details |
#2 | ACCEPTED | 0.95 s | 8.7 | details |
#3 | ACCEPTED | 0.94 s | 8.3 | details |
#4 | ACCEPTED | 0.94 s | 8.4 | details |
#5 | ACCEPTED | 0.96 s | 8.7 | details |
#6 | ACCEPTED | 0.95 s | 8.6 | details |
#7 | ACCEPTED | 0.94 s | 7.7 | details |
#8 | ACCEPTED | 0.94 s | 8.9 | details |
#9 | ACCEPTED | 0.95 s | 8.4 | details |
#10 | ACCEPTED | 0.95 s | 7.8 | details |
Code
#include <iostream>#include <cstdlib>#include <algorithm>#include <vector>#define F first#define S secondusing namespace std;typedef long long ll;const int N = 37e6;pair<ll, ll> t[111];ll mod = 98765431;ll asd = 1007;bool comp(pair<ll, ll> a, pair<ll, ll> b) {return a > b;}int main() {srand(time(0));ll rr = rand()%mod;int n;cin>>n;pair<ll, vector<int> > best = {1e18, {0}};ll sum = 0;ll mi = 1e9;for(int i = 0; i < n; ++i) {cin>>t[i].F;t[i].S = i;sum += t[i].F;mi = min(t[i].F, mi);}sort(t, t+n, comp);for(int i = 0; i < N/n; ++i) {//random_shuffle(t, t+n);ll a = sum/2;ll left = sum;vector<int> v(n);for(int j = 0; j < n; ++j) {rr *= asd;rr %= mod;ll r = rr%1000;//if(r/1000 < a/left) {if(r*left < 1000*a) {//if(r < 500) {left -= t[j].F;a -= t[j].F;v[t[j].S] = 1;}else {left -= t[j].F;v[t[j].S] = 2;}}a = abs(a);best = min(best, {a, v});}for(int i = 0; i < n; ++i) {cout<<best.S[i]<<' ';}cout<<'\n';}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
95 779724552 231968220 985023789 ... |
correct output |
---|
(empty) |
user output |
---|
1 1 1 1 2 2 2 2 2 2 1 2 2 1 2 ... |
Test 2
Verdict: ACCEPTED
input |
---|
85 229722261 51722691 862338862 8... |
correct output |
---|
(empty) |
user output |
---|
2 1 1 1 2 2 1 1 1 2 1 1 2 2 2 ... |
Test 3
Verdict: ACCEPTED
input |
---|
97 398995377 989444445 634573915 ... |
correct output |
---|
(empty) |
user output |
---|
1 1 1 1 1 1 1 2 2 1 2 1 1 2 2 ... |
Test 4
Verdict: ACCEPTED
input |
---|
99 843687873 164010938 51269970 4... |
correct output |
---|
(empty) |
user output |
---|
1 1 2 2 2 2 1 1 1 2 2 1 1 1 1 ... |
Test 5
Verdict: ACCEPTED
input |
---|
90 864611617 418460939 773297829 ... |
correct output |
---|
(empty) |
user output |
---|
2 2 1 1 2 2 2 1 2 1 1 2 2 1 1 ... |
Test 6
Verdict: ACCEPTED
input |
---|
92 289890246 25801423 763027596 7... |
correct output |
---|
(empty) |
user output |
---|
1 2 1 1 2 2 2 1 2 2 2 1 1 1 2 ... |
Test 7
Verdict: ACCEPTED
input |
---|
89 879039800 50522278 850785072 4... |
correct output |
---|
(empty) |
user output |
---|
1 1 2 2 1 1 1 1 2 2 2 1 1 1 2 ... |
Test 8
Verdict: ACCEPTED
input |
---|
96 27192469 222283781 681532515 1... |
correct output |
---|
(empty) |
user output |
---|
2 2 2 1 1 1 2 2 2 1 1 1 1 1 2 ... |
Test 9
Verdict: ACCEPTED
input |
---|
100 186459081 254674429 394007236 ... |
correct output |
---|
(empty) |
user output |
---|
1 1 2 1 2 1 1 1 1 2 1 2 1 2 2 ... |
Test 10
Verdict: ACCEPTED
input |
---|
98 612168861 979831717 671087051 ... |
correct output |
---|
(empty) |
user output |
---|
1 2 2 1 2 2 2 1 2 2 1 1 1 2 1 ... |