CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Omenat
Sender:OOliOO
Submission time:2016-01-24 00:06:08 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#148.3
Test results
testverdicttimescore
#1ACCEPTED0.14 s9.5details
#2ACCEPTED0.13 s9.5details
#3--0details
#4--0details
#5ACCEPTED0.12 s9.3details
#6ACCEPTED0.11 s10details
#7ACCEPTED0.12 s10details
#8--0details
#9--0details
#10--0details

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){
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(rand()%10==0&&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);
}
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 2 1 1 1 1 2 2 1 1 2 1 2 2 ...

Test 2

Verdict: ACCEPTED

input
85
229722261 51722691 862338862 8...

correct output
(empty)

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

Test 3

Verdict:

input
97
398995377 989444445 634573915 ...

correct output
(empty)

user output
(empty)

Test 4

Verdict:

input
99
843687873 164010938 51269970 4...

correct output
(empty)

user output
(empty)

Test 5

Verdict: ACCEPTED

input
90
864611617 418460939 773297829 ...

correct output
(empty)

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

Test 6

Verdict: ACCEPTED

input
92
289890246 25801423 763027596 7...

correct output
(empty)

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

Test 7

Verdict: ACCEPTED

input
89
879039800 50522278 850785072 4...

correct output
(empty)

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

Test 8

Verdict:

input
96
27192469 222283781 681532515 1...

correct output
(empty)

user output
(empty)

Test 9

Verdict:

input
100
186459081 254674429 394007236 ...

correct output
(empty)

user output
(empty)

Test 10

Verdict:

input
98
612168861 979831717 671087051 ...

correct output
(empty)

user output
(empty)