CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Omenat
Sender:
Submission time:2015-12-20 17:12:12 +0200
Language:C++
Status:READY
Result:85
Feedback
groupverdictscore
#1ACCEPTED84.9
Test results
testverdicttimescore
#1ACCEPTED0.43 s7.9details
#2ACCEPTED0.18 s9.1details
#3ACCEPTED0.51 s8.4details
#4ACCEPTED0.55 s8.7details
#5ACCEPTED0.29 s8.2details
#6ACCEPTED0.33 s8.4details
#7ACCEPTED0.28 s9details
#8ACCEPTED0.45 s7.9details
#9ACCEPTED0.65 s9.5details
#10ACCEPTED0.52 s7.8details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:199:10: warning: unused variable 't0' [-Wunused-variable]
  clock_t t0=clock();
          ^
input/code.cpp:206:5: warning: unused variable 'val' [-Wunused-variable]
  ll val=eval(v);
     ^

Code

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

ll p[111];
int n;
const ll inf=1e18;

ll eval(vector<int>&a){
	ll v1=0;
	ll v2=0;
	for (int i=0;i<n;i++){
		if (a[i]==1){
			v1+=p[i];
		}
		else{
			v2+=p[i];
		}
	}
	return llabs(v1-v2);
}

ll bvb;
int vvv[111];
int bvvv[111];

int rt[1111];
int ri=0;
inline int sl(){
	ri++;
	if (ri>=1007) ri=0;
	return rt[ri];
}

void dfs(vector<pair<ll, int> >&pp, int i, ll p1, ll p2){
	if (i==n){
		if (llabs(p1-p2)<bvb){
			bvb=llabs(p1-p2);
			for (int j=0;j<n;j++){
				bvvv[j]=vvv[j];
			}
		}
	}
	else{
		if (p1>p2){
			vvv[pp[i].S]=2;
			dfs(pp, i+1, p1, p2+pp[i].F);
			if (i<10||rand()%11==1){
				vvv[pp[i].S]=1;
				dfs(pp, i+1, p1+pp[i].F, p2);
			}
		}
		else{
			vvv[pp[i].S]=1;
			dfs(pp, i+1, p1+pp[i].F, p2);
			if (i<10||rand()%11==1){
				vvv[pp[i].S]=2;
				dfs(pp, i+1, p1, p2+pp[i].F);
			}
		}
	}
}

vector<int> solve3(){
	vector<pair<ll, int> > pp(n);
	vector<int> r(n);
	for (int i=0;i<n;i++){
		pp[i]={p[i], i};
	}
	sort(pp.rbegin(), pp.rend());
	bvb=inf;
	dfs(pp, 0, 0, 0);
	for (int i=0;i<n;i++){
		r[i]=bvvv[i];
	}
	return r;
}

vector<int> solve1(){
	vector<pair<ll, int> > pp(n);
	vector<int> r(n);
	for (int i=0;i<n;i++){
		pp[i]={p[i], i};
	}
	sort(pp.rbegin(), pp.rend());
	ll p1=0;
	ll p2=0;
	for (int i=0;i<n;i++){
		if (p1<p2){
			p1+=pp[i].F;
			r[pp[i].S]=1;
		}
		else{
			p2+=pp[i].F;
			r[pp[i].S]=2;
		}
	}
	return r;
}

int ps[111];
int ph[20][55];
int vv[111];

ll ss(int t){
	if (ps[t]==0) return 0;
	ll bv=inf;
	ll bvv=inf;
	int bb=0;
	for (int i=0;i<(1<<ps[t]);i++){
		ll v1=0;
		ll v2=0;
		for (int j=0;j<ps[t];j++){
			if (i&(1<<j)){
				v1+=p[ph[t][j]];
			}
			else{
				v2+=p[ph[t][j]];
			}
		}
		if (llabs(v1-v2)<bv){
			bv=llabs(v1-v2);
			bvv=v1-v2;
			bb=i;
		}
	}
	for (int j=0;j<ps[t];j++){
		if (bb&(1<<j)){
			vv[ph[t][j]]=1;
		}
		else{
			vv[ph[t][j]]=2;
		}
	}
	return bvv;
}

vector<int> solve2(int pk){
	int mp=(n-1)/pk+1;
	for (int i=0;i<mp;i++){
		ps[i]=0;
	}
	vector<int> asd(n);
	for (int i=0;i<n;i++){
		asd[i]=i/pk;
	}
	random_shuffle(asd.begin(), asd.end());
	for (int i=0;i<n;i++){
		int tp=asd[i];
		ph[tp][ps[tp]++]=i;
	}
	vector<ll> lol;
	for (int i=0;i<mp;i++){
		lol.push_back(ss(i));
	}
	int bb=0;
	ll bv=inf;
	for (int i=0;i<(1<<mp);i++){
		ll v=0;
		for (int j=0;j<mp;j++){
			if (i&(1<<j)){
				v-=lol[j];
			}
			else{
				v+=lol[j];
			}
		}
		if (llabs(v)<bv){
			bv=llabs(v);
			bb=i;
		}
	}
	vector<int> r(n);
	for (int j=0;j<mp;j++){
		if (bb&(1<<j)){
			for (int t=0;t<ps[j];t++){
				vv[ph[j][t]]=3-vv[ph[j][t]];
			}
		}
	}
	for (int i=0;i<n;i++){
		r[i]=vv[i];
	}
	return r;
}

int main(){
	srand(time(0));
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	for (int i=0;i<1007;i++){
		rt[i]=rand()%11;
	}
	cin>>n;
	//n=100;
	clock_t t0=clock();
	vector<pair<ll, int> > pp(n);
	for (int i=0;i<n;i++){
		cin>>p[i];
		//p[i]=rand();
	}
	vector<int> v=solve3();
	ll val=eval(v);
	/*
	while (1){
		vector<int> tv=solve2(10);
		if (eval(tv)<val){
			v=tv;
		}
		clock_t t1=clock();
		if (((double)(t1-t0)/CLOCKS_PER_SEC)>0.9) break;
	}
	*/
	for (int i=0;i<n;i++){
		cout<<v[i]<<" ";
	}
}

Test details

Test 1

Verdict: ACCEPTED

input
95
779724552 231968220 985023789 ...

correct output
(empty)

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

Test 2

Verdict: ACCEPTED

input
85
229722261 51722691 862338862 8...

correct output
(empty)

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

Test 3

Verdict: ACCEPTED

input
97
398995377 989444445 634573915 ...

correct output
(empty)

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

Test 4

Verdict: ACCEPTED

input
99
843687873 164010938 51269970 4...

correct output
(empty)

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

Test 5

Verdict: ACCEPTED

input
90
864611617 418460939 773297829 ...

correct output
(empty)

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

Test 6

Verdict: ACCEPTED

input
92
289890246 25801423 763027596 7...

correct output
(empty)

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

Test 7

Verdict: ACCEPTED

input
89
879039800 50522278 850785072 4...

correct output
(empty)

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

Test 8

Verdict: ACCEPTED

input
96
27192469 222283781 681532515 1...

correct output
(empty)

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

Test 9

Verdict: ACCEPTED

input
100
186459081 254674429 394007236 ...

correct output
(empty)

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

Test 10

Verdict: ACCEPTED

input
98
612168861 979831717 671087051 ...

correct output
(empty)

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