CSES - Datatähti 2017 alku - Results
Submission details
Task:Maalarit
Sender:Binäärihau
Submission time:2016-10-03 22:23:52 +0300
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED25
#3ACCEPTED31
#4ACCEPTED32
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.05 s1details
#3ACCEPTED0.05 s1details
#4ACCEPTED0.06 s1details
#5ACCEPTED0.06 s1details
#6ACCEPTED0.05 s1details
#7ACCEPTED0.07 s2details
#8ACCEPTED0.06 s2details
#9ACCEPTED0.06 s2details
#10ACCEPTED0.06 s2details
#11ACCEPTED0.05 s2details
#12ACCEPTED0.06 s2details
#13ACCEPTED0.06 s3details
#14ACCEPTED0.06 s3details
#15ACCEPTED0.06 s3details
#16ACCEPTED0.06 s3details
#17ACCEPTED0.06 s3details
#18ACCEPTED0.06 s3details
#19ACCEPTED0.11 s4details
#20ACCEPTED0.12 s4details
#21ACCEPTED0.11 s4details
#22ACCEPTED0.11 s4details
#23ACCEPTED0.11 s4details
#24ACCEPTED0.08 s4details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:172:9: warning: variable 'ansm' set but not used [-Wunused-but-set-variable]
     int ansm = 0;
         ^

Code

#include <bits/stdc++.h>
#define uint unsigned int
#define ull unsigned long long
#define INF 1000000001
#define LINF 1000000000000000001
#define ll long long
#define ld long double
#define M 1000000007
#define E 0.0000001
#define N (1<<17)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pdd pair<double, double>
#define pld pair<long double, long double>
#define cll complex<long long>
#define cld complex<long double>
#define X real()
#define Y imag()
#define C 'a'
#define F first
#define S second
#define PI 3.1415926535897932384626433
using namespace std;
ll v[2*N];
ll h[2*N];
void setv (int k, ll n) {
k += N;
v[k] = n;
for (k /= 2; k >= 1; k /= 2) v[k] = min(v[2 * k], v[2 * k + 1]);
}
void setv2 (int k, ll n) {
k += N;
h[k] = n;
for (k /= 2; k >= 1; k /= 2) h[k] = max(h[2 * k], h[2 * k + 1]);
}
ll lol (int a, int b) {
a += N;
b += N;
ll ans = LINF;
while (a <= b) {
if (a % 2) ans = min(ans, v[a++]);
if (b % 2 == 0) ans = min(ans, v[b--]);
a /= 2;
b /= 2;
}
return ans;
}
ll asd (int a, int b) {
a += N;
b += N;
ll ans = 0;
while (a <= b) {
if (a % 2) ans = max(ans, h[a++]);
if (b % 2 == 0) ans = max(ans, h[b--]);
a /= 2;
b /= 2;
}
return ans;
}
set<pair<pii, pair<int, ll>>> s;
ll m = 0;
int it = 1;
int n;
int c[N];
ll g[N];
set<pair<pii, pair<int, ll>>>::iterator q1;
set<pair<pii, pair<int, ll>>>::iterator q2;
void split (int i, bool b) {
auto p = s.upper_bound({{i, INF}, {INF, LINF}});
--p;
auto f = *p;
s.erase(p);
int x = f.first.first;
int y = f.first.second;
int z = f.second.first;
setv2(z, 0);
if (x != i) {
ll t = (x != 1) * lol(x, i - 1);
s.insert({{x, i - 1}, {++it, t}});
if (((i - 1 - x) % 2 == 0) != b) t = 0;
setv2(it, t);
}
if (y != i) {
ll t = (y != n) * lol(i + 1, y);
//cout<<y<<" x "<<n<<endl;
//cout<<i + 1<<" "<<y<<" -> "<<t<<endl;
s.insert({{i + 1, y}, {++it, t}});
if (((i + 1 - y) % 2 == 0) != b) t = 0;
setv2(it, t);
}
q1 = q2 = s.end();
if (b) {
if (x != i) q1 = s.lower_bound({{x, 0}, {0, 0}});
if (y != i) q2 = s.lower_bound({{i + 1, 0}, {0, 0}});
}
m = asd(1, it);
}
int brans[N];
ll brmin = LINF;
int bra = 0;
void brute2 (int n, int i, int v[], int c[], int r, int g, int b, int p) {
if (n == i) {
if (r + g + b < brmin) {
brmin = r + g + b;
bra = (r > 0) + (g > 0) + (b > 0);
for (int j = 0; j < n; j++) brans[j] = c[j];
}
return;
}
for (int j = 1; j <= 3; j++) {
if (j == p) continue;
c[i] = j;
brute2(n, i + 1, v, c, j == 1 ? max(r, v[i]) : r, j == 2 ? max(g, v[i]) : g, j == 3 ? max(b, v[i]) : b, j);
}
}
void brute (int n, int v[]) {
int c[n];
for (int i = 0; i < n; i++) c[i] = 0;
c[0] = 1;
brute2(n, 1, v, c, v[0], 0, 0, 1);
cout<<brmin<<" "<<bra<<endl;
for (int i = 0; i < n; i++) cout<<brans[i]<<" ";
cout<<endl;
}
int main () {
srand(time(0));
n = 16;
cin>>n;
//cout<<n<<endl;
int q[n];
for (int i = 0; i < 2 * N; i++) v[i] = LINF;
vector<pair<ll, int>> w;
for (int i = 0; i < n; i++) {
ll x = (rand() % 100) + 1;
//cout<<x<<" ";
cin>>x;
setv(i + 1, x);
w.push_back({x, i + 1});
g[i] = x;
q[i] = x;
}
//cout<<endl;
if (n <= 10) brute(n, q), exit(0);
sort(w.rbegin(), w.rend());
int ii = 0;
for (int i = 0; i < n; i++) {
if (w[ii].first != w[i].first) {
random_shuffle(w.begin() + ii, w.begin() + i);
ii = i;
}
}
random_shuffle(w.begin() + ii, w.begin() + n);
s.insert({{1, n}, {it, lol(1, n)}});
split(w[0].second, false);
c[w[0].second] = 1;
ll ans = LINF;
int ansm = 0;
int ansi = 1;
for (int i = 1; i <= n; i++) {
int x = w[i].second;
//cout<<"SPLIT "<<x<<endl;
split(x, true);
//cout<<"DEBUG "<<w[0].first<<" "<<w[i].first<<" "<<m<<endl;
if (ans > w[0].first + w[i].first + m) {
ans = w[0].first + w[i].first + m;
ansi = i;
ansm = m;
}
if (q1 != s.end()) {
int p = q1->second.first;
ll t = q1->second.second;
setv2(p, t - asd(p, p));
}
if (q2 != s.end()) {
int p = q2->second.first;
ll t = q2->second.second;
setv2(p, t - asd(p, p));
}
if (c[x - 1] || c[x + 1]) break;
c[x] = 1;
}
ll me, mo;
me = mo = 0;
for (int i = 0; i < n; i++) {
if (i % 2) me = max(me, g[i]);
else mo = max(mo, g[i]);
}
if (me + mo <= ans) {
cout<<me + mo<<" "<<(me > 0) + (mo > 0)<<endl;
for (int i = 0; i < n; i++) cout<<(i % 2) + 1<<" ";
cout<<endl;
} else {
//cout<<ansm<<" "<<w[ansi].first<<" "<<w[0].first<<endl;
for (int i = 1; i <= n; i++) {
c[i] = 0;
}
for (int i = 0; i < ansi; i++) {
c[w[i].second] = 1;
}
c[w[ansi].second] = 2;
int a = 1;
for (int b = 1; b <= n; b++) {
if (c[b]) {
if (a == 1) {
for (int i = 1; i < b; i++) {
if ((b - i) % 2 == 1) c[i] = 3 - c[b];
else c[i] = c[b];
}
} else {
if (c[b] == c[a - 1]) {
if ((b - a) % 2 == 0) {
int mi = a;
for (int i = a; i < b; i++) {
if (g[i - 1] < g[mi - 1]) mi = i;
}
c[mi] = 3;
for (int i = a; i < mi; i++) {
if ((i - a) % 2 == 0) c[i] = 3 - c[a - 1];
else c[i] = c[a - 1];
}
for (int i = mi + 1; i < b; i++) {
if ((b - i) % 2 == 1) c[i] = 3 - c[b];
else c[i] = c[b];
}
} else {
for (int i = a; i < b; i++) {
if ((b - i) % 2 == 1) c[i] = 3 - c[b];
else c[i] = c[b];
}
}
} else {
if ((b - a) % 2 == 0) {
for (int i = a; i < b; i++) {
if ((b - i) % 2 == 1) c[i] = 3 - c[b];
else c[i] = c[b];
}
} else {
int mi = a;
for (int i = a; i < b; i++) {
if (g[i - 1] < g[mi - 1]) mi = i;
}
c[mi] = 3;
for (int i = a; i < mi; i++) {
if ((i - a) % 2 == 0) c[i] = 3 - c[a - 1];
else c[i] = c[a - 1];
}
for (int i = mi + 1; i < b; i++) {
if ((b - i) % 2 == 1) c[i] = 3 - c[b];
else c[i] = c[b];
}
}
}
}
a = b + 1;
} else if (b == n) {
for (int i = a; i <= b; i++) {
if ((i - a) % 2 == 0) c[i] = 3 - c[a - 1];
else c[i] = c[a - 1];
}
}
}
ll f[] = {0, 0, 0};
for (int i = 1; i <= n; i++) f[c[i] - 1] = max(f[c[i] - 1], (ll)q[i - 1]);
cout<<f[0] + f[1] + f[2]<<" "<<3 - (f[2] == 0)<<endl;
for (int i = 1; i <= n; i++) cout<<c[i]<<" ";
cout<<endl;
}
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10
22 54 3 91 69 90 40 29 83 71

correct output
174 3
2 1 2 1 2 1 2 1 2 1 

user output
174 2
1 2 1 2 1 2 1 2 1 2 

Test 2

Group: 1

Verdict: ACCEPTED

input
10
49 3 96 38 90 18 92 74 83 1

correct output
170 3
1 2 1 2 1 2 1 2 1 2 

user output
170 2
1 2 1 2 1 2 1 2 1 2 

Test 3

Group: 1

Verdict: ACCEPTED

input
10
46 3 41 30 16 17 12 93 80 81

correct output
173 3
2 1 2 1 2 1 2 1 2 1 

user output
173 2
1 2 1 2 1 2 1 2 1 2 

Test 4

Group: 1

Verdict: ACCEPTED

input
10
46 8 95 85 82 73 82 92 53 90

correct output
187 3
1 2 1 2 1 2 1 2 1 2 

user output
187 2
1 2 1 2 1 2 1 2 1 2 

Test 5

Group: 1

Verdict: ACCEPTED

input
10
41 18 61 59 40 96 5 2 74 38

correct output
159 3
2 1 2 1 2 1 2 3 1 2 

user output
159 3
1 2 1 2 1 2 1 3 2 1 

Test 6

Group: 1

Verdict: ACCEPTED

input
10
1 1 1 1 1 1 1 1 1 1

correct output
2 3
2 1 2 1 2 1 2 1 2 1 

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

Test 7

Group: 2

Verdict: ACCEPTED

input
100
1 39 94 5 24 84 84 10 78 61 38...

correct output
193 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

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

Test 8

Group: 2

Verdict: ACCEPTED

input
100
31 73 18 88 49 28 66 5 32 48 9...

correct output
199 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

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

Test 9

Group: 2

Verdict: ACCEPTED

input
100
45 56 36 60 31 10 23 79 29 17 ...

correct output
198 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

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

Test 10

Group: 2

Verdict: ACCEPTED

input
100
1 77 70 62 21 68 40 54 90 62 1...

correct output
194 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

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

Test 11

Group: 2

Verdict: ACCEPTED

input
100
4 47 41 81 56 64 12 10 20 100 ...

correct output
189 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

user output
189 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

Test 12

Group: 2

Verdict: ACCEPTED

input
10
1 1 1 1 1 1 1 1 1 1

correct output
2 3
2 1 2 1 2 1 2 1 2 1 

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

Test 13

Group: 3

Verdict: ACCEPTED

input
100
256160448 813097800 167146270 ...

correct output
1929869257 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

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

Test 14

Group: 3

Verdict: ACCEPTED

input
100
520002672 3542567 24668528 959...

correct output
1946957555 3
1 2 3 1 2 1 2 1 2 1 2 1 2 1 2 ...

user output
1946957555 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

Test 15

Group: 3

Verdict: ACCEPTED

input
100
483158423 780224665 844754665 ...

correct output
1959373560 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

user output
1959373560 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

Test 16

Group: 3

Verdict: ACCEPTED

input
100
969647264 128558017 889036329 ...

correct output
1997942264 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

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

Test 17

Group: 3

Verdict: ACCEPTED

input
100
745018527 400495893 635468795 ...

correct output
1961391143 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

user output
1961391143 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

Test 18

Group: 3

Verdict: ACCEPTED

input
10
1 1 1 1 1 1 1 1 1 1

correct output
2 3
2 1 2 1 2 1 2 1 2 1 

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

Test 19

Group: 4

Verdict: ACCEPTED

input
100000
197349274 775463806 263930657 ...

correct output
1999942635 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

user output
1999942635 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

Test 20

Group: 4

Verdict: ACCEPTED

input
100000
102296405 34648120 320393597 9...

correct output
1999930943 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

user output
1999930943 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

Test 21

Group: 4

Verdict: ACCEPTED

input
100000
781254921 418252056 502363453 ...

correct output
1999987794 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

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

Test 22

Group: 4

Verdict: ACCEPTED

input
100000
849784881 230439009 455097426 ...

correct output
1999979439 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

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

Test 23

Group: 4

Verdict: ACCEPTED

input
100000
851456132 13422224 537539701 4...

correct output
1999948226 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

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

Test 24

Group: 4

Verdict: ACCEPTED

input
100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
2 3
3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 ...

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