Task: | Maalarit |
Sender: | Binäärihau |
Submission time: | 2016-10-03 22:23:52 +0300 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 25 |
#3 | ACCEPTED | 31 |
#4 | ACCEPTED | 32 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.06 s | 1 | details |
#2 | ACCEPTED | 0.05 s | 1 | details |
#3 | ACCEPTED | 0.05 s | 1 | details |
#4 | ACCEPTED | 0.06 s | 1 | details |
#5 | ACCEPTED | 0.06 s | 1 | details |
#6 | ACCEPTED | 0.05 s | 1 | details |
#7 | ACCEPTED | 0.07 s | 2 | details |
#8 | ACCEPTED | 0.06 s | 2 | details |
#9 | ACCEPTED | 0.06 s | 2 | details |
#10 | ACCEPTED | 0.06 s | 2 | details |
#11 | ACCEPTED | 0.05 s | 2 | details |
#12 | ACCEPTED | 0.06 s | 2 | details |
#13 | ACCEPTED | 0.06 s | 3 | details |
#14 | ACCEPTED | 0.06 s | 3 | details |
#15 | ACCEPTED | 0.06 s | 3 | details |
#16 | ACCEPTED | 0.06 s | 3 | details |
#17 | ACCEPTED | 0.06 s | 3 | details |
#18 | ACCEPTED | 0.06 s | 3 | details |
#19 | ACCEPTED | 0.11 s | 4 | details |
#20 | ACCEPTED | 0.12 s | 4 | details |
#21 | ACCEPTED | 0.11 s | 4 | details |
#22 | ACCEPTED | 0.11 s | 4 | details |
#23 | ACCEPTED | 0.11 s | 4 | details |
#24 | ACCEPTED | 0.08 s | 4 | details |
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.1415926535897932384626433using 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 ... |