CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Omenat
Sender:
Submission time:2015-12-20 17:01:08 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttimescore
#10.19 s0details
#20.19 s0details
#30.18 s0details
#40.20 s0details
#50.20 s0details
#60.17 s0details
#70.19 s0details
#80.19 s0details
#90.20 s0details
#100.19 s0details

Code

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define F first
#define S second
using namespace std;
typedef unsigned long long ll;
const int N = 45e6;
pair<ll, ll> t[111];
ll mod = (1<<30)-1;
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;
//if(r/1000 < a/left) {
if(r*left < mod*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;
}
if(-a > best.F) break;
}
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:

input
95
779724552 231968220 985023789 ...

correct output
(empty)

user output
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 ...

Test 2

Verdict:

input
85
229722261 51722691 862338862 8...

correct output
(empty)

user output
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

Test 3

Verdict:

input
97
398995377 989444445 634573915 ...

correct output
(empty)

user output
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

Test 4

Verdict:

input
99
843687873 164010938 51269970 4...

correct output
(empty)

user output
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

Test 5

Verdict:

input
90
864611617 418460939 773297829 ...

correct output
(empty)

user output
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

Test 6

Verdict:

input
92
289890246 25801423 763027596 7...

correct output
(empty)

user output
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

Test 7

Verdict:

input
89
879039800 50522278 850785072 4...

correct output
(empty)

user output
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

Test 8

Verdict:

input
96
27192469 222283781 681532515 1...

correct output
(empty)

user output
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

Test 9

Verdict:

input
100
186459081 254674429 394007236 ...

correct output
(empty)

user output
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

Test 10

Verdict:

input
98
612168861 979831717 671087051 ...

correct output
(empty)

user output
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...