CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Omenat
Sender:
Submission time:2015-12-20 17:13:20 +0200
Language:C++
Status:READY
Result:72
Feedback
groupverdictscore
#1ACCEPTED71.7
Test results
testverdicttimescore
#1ACCEPTED0.96 s7.3details
#2ACCEPTED0.98 s6.2details
#3ACCEPTED0.99 s7.4details
#4ACCEPTED0.98 s6.5details
#5ACCEPTED0.97 s7.1details
#6ACCEPTED0.97 s7.2details
#7ACCEPTED0.99 s8.3details
#8ACCEPTED0.98 s6.8details
#9ACCEPTED0.98 s7.3details
#10ACCEPTED0.97 s7.6details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:19:25: warning: variable 'rr' set but not used [-Wunused-but-set-variable]
     unsigned long long  rr = rand()%mod;
                         ^

Code

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N = 30e6;
pair<ll, ll> t[111];
unsigned long long mod = (1<<23)-1;;
//ll mod = 98765431;
ll asd = 1007;
bool comp(pair<ll, ll> a, pair<ll, ll> b) {
    return a > b;
}
int main() {
    srand(time(0));
    unsigned long long  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);
    ll q1 = 0;
    ll q2 = 0;
    for(int i = 0; i < N/n; ++i) {
        random_shuffle(t, t+n);
        rr = rand()%mod;
        ll a = sum/2;
        ll left = sum;
        vector<int> v(n);
        for(int j = 0; j < n; ++j) {
            /*
            rr *= asd;
            rr += 323121;
            rr %= mod;
            ll r = rr;
            */
            //if(r/1000 < a/left) {
            //if(r*left < mod*a) {
            if(q1 < q2) {
            //if(r < 500) {
                left -= t[j].F;
                a -= t[j].F;
                v[t[j].S] = 1;
                q1 += t[j].F;
            }
            else {
                q2 += t[j].F;
                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
2 2 2 1 2 1 2 2 2 1 2 1 1 2 1 ...

Test 2

Verdict: ACCEPTED

input
85
229722261 51722691 862338862 8...

correct output
(empty)

user output
1 1 1 1 1 2 2 2 1 2 2 2 2 2 2 ...

Test 3

Verdict: ACCEPTED

input
97
398995377 989444445 634573915 ...

correct output
(empty)

user output
2 1 2 1 2 2 1 2 2 1 2 1 2 1 1 ...

Test 4

Verdict: ACCEPTED

input
99
843687873 164010938 51269970 4...

correct output
(empty)

user output
1 2 2 2 2 2 1 1 1 2 1 2 1 2 1 ...

Test 5

Verdict: ACCEPTED

input
90
864611617 418460939 773297829 ...

correct output
(empty)

user output
2 2 1 2 2 2 2 2 2 2 1 1 2 2 2 ...

Test 6

Verdict: ACCEPTED

input
92
289890246 25801423 763027596 7...

correct output
(empty)

user output
2 2 1 1 2 1 2 2 2 2 1 1 1 2 1 ...

Test 7

Verdict: ACCEPTED

input
89
879039800 50522278 850785072 4...

correct output
(empty)

user output
2 1 1 2 2 1 2 1 1 2 1 2 1 1 1 ...

Test 8

Verdict: ACCEPTED

input
96
27192469 222283781 681532515 1...

correct output
(empty)

user output
2 2 1 1 2 2 1 2 1 1 2 2 1 2 1 ...

Test 9

Verdict: ACCEPTED

input
100
186459081 254674429 394007236 ...

correct output
(empty)

user output
1 2 1 2 1 1 2 1 2 2 2 1 2 2 2 ...

Test 10

Verdict: ACCEPTED

input
98
612168861 979831717 671087051 ...

correct output
(empty)

user output
2 1 2 1 1 1 1 2 2 1 1 2 2 2 2 ...