CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Omenat
Sender:OOliOO
Submission time:2016-01-24 00:01:00 +0200
Language:C++
Status:READY
Result:93
Feedback
groupverdictscore
#1ACCEPTED92.5
Test results
testverdicttimescore
#1ACCEPTED0.96 s9details
#2ACCEPTED0.88 s8.7details
#3ACCEPTED0.97 s10details
#4ACCEPTED0.95 s8.6details
#5ACCEPTED0.94 s8.8details
#6ACCEPTED0.90 s10details
#7ACCEPTED0.90 s8.9details
#8ACCEPTED0.98 s9.5details
#9ACCEPTED0.96 s10details
#10ACCEPTED0.96 s9details

Code

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <unordered_set>
#include <stdio.h>
#include <string.h>
#include <unordered_map>
#include <fstream>
#include <set>
#include <map>

#define MOD 1000000007
#define ll long long
//#define N (1<<50)
#define float double
#define str string

using namespace std;

struct lol{
    vector<int> o1,o2;
    ll diff;
};

bool operator<(lol a, lol b){
    if(a.diff==b.diff)
        return a.o1[0]<b.o1[0];
    return a.diff<b.diff;
}

lol op(lol a, lol b){
    if(a<b)
        return op(b,a);
    lol c;
    c.diff=a.diff-b.diff;

    for(auto asd:a.o1)
        c.o1.push_back(asd);
    for(auto asd:a.o2)
        c.o2.push_back(asd);
    for(auto asd:b.o1)
        c.o2.push_back(asd);
    for(auto asd:b.o2)
        c.o1.push_back(asd);

    return c;
}

lol op2(lol a, lol b){
    lol c;
    c.diff=a.diff+b.diff;

    for(auto asd:a.o1)
        c.o1.push_back(asd);
    for(auto asd:a.o2)
        c.o2.push_back(asd);
    for(auto asd:b.o1)
        c.o1.push_back(asd);
    for(auto asd:b.o2)
        c.o2.push_back(asd);

    return c;
}

int vast[100];


lol parsa;
set<lol> kek;
int c;
void etsi(ll js){
    if(parsa.diff <=2*(kek.rbegin()->diff)-js)
        return;

    c++;
    if(c>=150000)
        return;

    if(kek.size()==1){
        if(kek.begin()->diff < parsa.diff)
            parsa=*kek.begin();
        return;
    }

    lol a=*kek.rbegin();
    kek.erase(a);
    lol b=*kek.rbegin();
    kek.erase(b);


    lol c2=op(a,b);
    kek.insert(c2);
    etsi(js-b.diff);
    kek.erase(c2);

    if(js>2*a.diff){
        lol c1=op2(a,b);
        kek.insert(c1);
        etsi(js);
        kek.erase(c1);
    }

    kek.insert(a);
    kek.insert(b);
}

int main(){
    parsa.diff=1000000000000000000ll;
    int n;
    cin>>n;

    ll os=0;

    for(int i=0; i<n; i++){
        lol uus;
        ll w;
        cin>>w;
        os+=w;
        uus.diff=w;
        uus.o1.push_back(i);
        kek.insert(uus);
    }

    /**while(pq.size()>=2){
        lol a,b;
        a=pq.top();
        pq.pop();
        b=pq.top();
        pq.pop();

        pq.push(op(a,b));
    }*/

    etsi(os);

    for(int i:parsa.o1)
        vast[i]=1;
    for(int i:parsa.o2)
        vast[i]=2;

    for(int i=0; i<n; i++)
        cout<<vast[i]<<" ";
    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
95
779724552 231968220 985023789 ...

correct output
(empty)

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

Test 2

Verdict: ACCEPTED

input
85
229722261 51722691 862338862 8...

correct output
(empty)

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

Test 3

Verdict: ACCEPTED

input
97
398995377 989444445 634573915 ...

correct output
(empty)

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

Test 4

Verdict: ACCEPTED

input
99
843687873 164010938 51269970 4...

correct output
(empty)

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

Test 5

Verdict: ACCEPTED

input
90
864611617 418460939 773297829 ...

correct output
(empty)

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

Test 6

Verdict: ACCEPTED

input
92
289890246 25801423 763027596 7...

correct output
(empty)

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

Test 7

Verdict: ACCEPTED

input
89
879039800 50522278 850785072 4...

correct output
(empty)

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

Test 8

Verdict: ACCEPTED

input
96
27192469 222283781 681532515 1...

correct output
(empty)

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

Test 9

Verdict: ACCEPTED

input
100
186459081 254674429 394007236 ...

correct output
(empty)

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

Test 10

Verdict: ACCEPTED

input
98
612168861 979831717 671087051 ...

correct output
(empty)

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