Task: | Maalarit |
Sender: | yhyy |
Submission time: | 2016-10-03 12:39:16 +0300 |
Language: | C++ |
Status: | READY |
Result: | 12 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | WRONG ANSWER | 0 |
#3 | WRONG ANSWER | 0 |
#4 | RUNTIME ERROR | 0 |
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.06 s | 1 | details |
#7 | ACCEPTED | 0.05 s | 2 | details |
#8 | ACCEPTED | 0.06 s | 2 | details |
#9 | ACCEPTED | 0.05 s | 2 | details |
#10 | ACCEPTED | 0.05 s | 2 | details |
#11 | WRONG ANSWER | 0.06 s | 2 | details |
#12 | ACCEPTED | 0.05 s | 2 | details |
#13 | WRONG ANSWER | 0.06 s | 3 | details |
#14 | WRONG ANSWER | 0.05 s | 3 | details |
#15 | WRONG ANSWER | 0.05 s | 3 | details |
#16 | WRONG ANSWER | 0.06 s | 3 | details |
#17 | WRONG ANSWER | 0.07 s | 3 | details |
#18 | ACCEPTED | 0.06 s | 3 | details |
#19 | RUNTIME ERROR | 0.14 s | 4 | details |
#20 | RUNTIME ERROR | 0.19 s | 4 | details |
#21 | RUNTIME ERROR | 0.14 s | 4 | details |
#22 | RUNTIME ERROR | 0.14 s | 4 | details |
#23 | RUNTIME ERROR | 0.17 s | 4 | details |
#24 | WRONG ANSWER | 0.06 s | 4 | details |
Code
#include <iostream> #include <algorithm> #include <set> using namespace std; #define F first #define S second #define N 128 int n, t[101], h[101], a, b=1e9, c=1e9, tt[2*N], yhyy[101]; pair<int,int> p[101]; set<int> s; multiset<int> s2; void juttu() { for(int i=1; i<=n; ++i){ if(t[i]>b) yhyy[i]=1; } for(int i=1; i<=n; ++i){ if(yhyy[i]==0 && yhyy[i-1]==1 && t[i]>c) yhyy[i]=2; if(yhyy[i]==0 && yhyy[i-1]==2 && t[i]>c) yhyy[i]=1; } for(int i=n; i>=0; --i){ if(yhyy[i]==0 && yhyy[i+1]==1 && t[i]>c) yhyy[i]=2; else if(yhyy[i]==0 && t[i]>c) yhyy[i]=1; }for(int i=1; i<=n; ++i){ if(yhyy[i]==0){ if(yhyy[i-1]+yhyy[i+1]<3) yhyy[i]=2; else if(yhyy[i-1]+yhyy[i+1]>3) yhyy[i]=1; } } } int laske(){ multiset<int>::iterator it = s2.end(); --it; return *it; } void upd(int k){ set<int>::iterator it = s.lower_bound(k); int A, B; if(it==s.end()) B=-1; else B=*it; if(it==s.begin()) A=-1; else { --it; A=*it; } int a= A+N, b=B+N, V=1e9; if(A>-1 && B>-1 && (b-a+1)%2==0){ while(a<=b){ if(a%2==1) V=min(V, tt[a++]); if(b%2==0) V=min(V, tt[b--]); a/=2, b/=2; } s2.erase(s2.find(V)); } a= A+N, b=k+N, V=1e9; if(A>-1 && (b-a+1)%2==0){ while(a<=b){ if(a%2==1) V=min(V, tt[a++]); if(b%2==0) V=min(V, tt[b--]); a/=2, b/=2; } s2.insert(V); } a= k+N, b=B+N, V=1e9; if(B>-1 && (b-a+1)%2==0){ while(a<=b){ if(a%2==1) V=min(V, tt[a++]); if(b%2==0) V=min(V, tt[b--]); a/=2, b/=2; } s2.insert(V); } s.insert(k); } int main(){ cin >> n; for(int i=1; i<=n; ++i) cin >> t[i], p[i]={t[i], i}; for(int i=0; i<2*N; ++i) tt[i]=1e9; for(int i=1; i<=n; ++i){ int k=N+i; tt[k]=t[i]; for(k/=2; k>=1; k/=2) tt[k]=min(tt[2*k], tt[2*k+1]); } if(n==1) {cout << t[1] << " 1\n1";return 0;} sort(p+1, p+n+1); reverse(p+1, p+n+1); a=p[1].F; h[p[1].S]=1; s.insert(p[1].S); s2.insert(0); for(int i=2; i<=n; ++i){ int c1 = laske(); if(a+p[i].F+c1 < a+b+c) b=p[i].F, c=c1; if(h[p[i].S-1]+h[p[i].S+1]>0) break; h[p[i].S]=1; upd(p[i].S); } if(c==0){ cout << a+b << " 2\n"; for(int i=1; i<=n; ++i) cout << i%2+1 << " "; return 0; } juttu(); cout << a+b+c << " 3\n"; for(int i=0; i<n; ++i) cout << yhyy[i+1]+1 << " "; }
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 2 1 2 1 2 1 2 1 2 1 |
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 2 1 2 1 2 1 2 1 2 1 |
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 2 1 2 1 2 1 2 1 2 1 |
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 2 1 2 1 2 1 2 1 2 1 |
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 3 2 3 2 3 2 3 1 2 3 |
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 2 1 2 1 2 1 2 1 2 1 |
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 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
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 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
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 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
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 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
Test 11
Group: 2
Verdict: WRONG ANSWER
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 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 ... |
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 2 1 2 1 2 1 2 1 2 1 |
Test 13
Group: 3
Verdict: WRONG ANSWER
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 |
---|
-2076370651 3 3 2 3 3 1 2 3 1 2 3 2 3 2 3 2 ... |
Test 14
Group: 3
Verdict: WRONG ANSWER
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 |
---|
-1307323366 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ... |
Test 15
Group: 3
Verdict: WRONG ANSWER
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 |
---|
-1301786517 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ... |
Test 16
Group: 3
Verdict: WRONG ANSWER
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 |
---|
-1846966078 3 2 3 2 3 3 3 1 2 3 3 3 2 3 2 3 ... |
Test 17
Group: 3
Verdict: WRONG ANSWER
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 |
---|
-1300199333 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ... |
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 2 1 2 1 2 1 2 1 2 1 |
Test 19
Group: 4
Verdict: RUNTIME ERROR
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 |
---|
(empty) |
Test 20
Group: 4
Verdict: RUNTIME ERROR
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 |
---|
(empty) |
Test 21
Group: 4
Verdict: RUNTIME ERROR
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 |
---|
(empty) |
Test 22
Group: 4
Verdict: RUNTIME ERROR
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 |
---|
(empty) |
Test 23
Group: 4
Verdict: RUNTIME ERROR
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 |
---|
(empty) |
Test 24
Group: 4
Verdict: WRONG ANSWER
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 |
---|
1 1 1 |