CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Omenat
Sender:
Submission time:2015-12-21 12:22:27 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttimescore
#1--0details
#2--0details
#3--0details
#4--0details
#5--0details
#6--0details
#7--0details
#8--0details
#9--0details
#10--0details

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
using namespace std;
int n;
vector<pair<int, int> > p;
bool srt(pair<int, int> a, pair<int, int> b){ return a.first>b.first;}
int jako[101];
int tulos[101];
long long paras;
const int G=1010101;
const int B=21;
bool good[G][22];
int main(){
srand (time(NULL));
long long paras=100000000000000ll;
cin >> n;
long long s=0;
for (int i=0; i<n; ++i){
int x;
cin >> x;
s+=x;
p.push_back(make_pair(x, i));
}sort(p.begin(), p.end(), srt);
for (int i=0; i<=min(20, n-B); ++i){
for (int j=0; j<G; ++j){
if (good[j][i]){
int nv=p[n-1-i].first+j;
if (nv<G) good[nv][i+1]=1;
}
}
}
for (int i=0; i<G; ++i){
for (int j=0; j<=20; ++j){
if (good[i][j]) good[i][j+1]=1;
}
}
int b=min(n, B);
int bt=1<<b;
long long sa;
long long sb;
for (int i=0; i<bt; ++i){
sa=0; sb=0;
for (int j=0; j<n; ++j){
if (j<b){
if (i&(1<<j)){
sa+=p[j].first;
jako[j]=1;
}else{
sb+=p[j].first;
jako[j]=2;
}
}else{
long long cp1=s/2-sa;
long long cp2=s/2-sb;
long long p1=s/2-sa-p[j].first;
long long p2=s/2-sb-p[j].first;
int gi=n-j-1;
if (gi>20) gi=20;
bool j1=0;
if (0<=p1 && p1<G && good[p1][gi]){
j1=1;
}else if (0<=p2 && p2<G && good[p2][gi]){
j1=0;
}else if (0<=cp1 && cp1<G && good[cp1][gi]){
j1=0;
}else if (0<=cp2 && cp2<G && good[cp2][gi]){
j1=1;
}else{
if (sa<sb) j1=1;
else j1=0;
}
if (j1){
sa+=p[j].first;
jako[j]=1;
}else{
sb+=p[j].first;
jako[j]=2;
}
}
}
long long d=sa-sb;
if (d<0) d=-d;
if (d<paras){
for (int j=0; j<n; ++j){
tulos[p[j].second]=jako[j];
}
paras=d;
}
if (paras==0) break;
}
for (int i=0; i<n; ++i) cout << tulos[i] << "\n";
}

Test details

Test 1

Verdict:

input
95
779724552 231968220 985023789 ...

correct output
(empty)

user output
(empty)

Test 2

Verdict:

input
85
229722261 51722691 862338862 8...

correct output
(empty)

user output
(empty)

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:

input
90
864611617 418460939 773297829 ...

correct output
(empty)

user output
(empty)

Test 6

Verdict:

input
92
289890246 25801423 763027596 7...

correct output
(empty)

user output
(empty)

Test 7

Verdict:

input
89
879039800 50522278 850785072 4...

correct output
(empty)

user output
(empty)

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)