답안 #32046 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32046	2017-09-23T10:48:45 Z	osmanorhan	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	173 ms	45292 KB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define all( x ) x.begin(), x.end()
#define umin( x, y ) x = min( x, (y) )
#define umax( x, y ) x = max( x, (y) )
#define pb push_back

using namespace std;

typedef long long Lint;
typedef pair<int,int> ii;

const int inf = 1e9 + 137;
const int maxn = 200020;

int a, n;
ii segment[maxn*3];
vector<ii> inc, de;
vector<int> s, ti;

ii find( int l, int r ) {
    ii t = ii( inf, n+1 );
    for(l+=n, r+=n;l<=r;l=(l+1)>>1, r=(r-1)>>1) {
        if( l&1 ) umin( t, segment[l] );
        if( ~r&1 ) umin( t, segment[r] );
    }
    return t;
}

Lint dn[1<<17][20];
int used[1<<17][20];

Lint f( int n, int last ) {
    if( n == (1<<a)-1 ) return 0;
    if( used[n][last] ) return dn[n][last];
    used[n][last] = 1;
    Lint now = ti[last];
    Lint ret = 1e18;
    for(int i=0;i<a;i++)
        if( !((1<<i)&n) ) {
            umin( ret, f( n|(1<<i), i ) + max( 0ll, now-s[i] ) );
        }
    return dn[n][last] = ret;
}

bool comp( const ii &a, const ii &b ) {
    return a.se < b.se;
}

Lint plan_roller_coaster(vector<int> S, vector<int> Ti) {
    s = S;
    ti = Ti;
    a = s.size();

    if( s.size() < 17 ) {
        ti.pb( 1 );
        return f( 0, a );
    }
    for(int i=0;i<a;i++) {
        if( s[i] > ti[i] ) de.pb( ii( ti[i], s[i] ) );
        else inc.pb( ii( s[i], ti[i] ) );
    }
    sort( all( inc ) );
    sort( all( de ), comp );

    n = 1;
    while( n < inc.size() ) n <<= 1;

    for(int i=1;i<n+n;i++)
        segment[i] = ii( inf, n+1 );

    for(int i=0;i<inc.size();i++)
        segment[i+n] = ii( inc[i].se, i );

    for(int i=n-1;i>=1;i--)
        segment[i] = min( segment[i+i], segment[i+i+1] );

    for(int i=0,now=1;i<de.size();i++) {
        int last = de[i].se;
        //printf("asd--  %d %d\n",last,inc.size());
        bool flag = 1;
        int go = now;
        while( flag ) {
            ii t = find( lower_bound( all( inc ), ii( go, 0 ) ) - inc.begin(), n-1 );
                //printf("--- %d %d -- %d %d\n",t.fi,last,go,n-1);
            if( t.fi <= last ) {
                segment[t.se+n] = ii( inf, n+1 );
                for(int k=(t.se+n)>>1;k;k>>=1)
                    segment[k] = min( segment[k+k], segment[k+k+1] );
                go = t.fi;
            } else break;
        }
        now = de[i].fi;
    }
    ii t = find( 0, n-1 );
    if( t.fi >= inf ) return 0;
    return 1;
}

Compilation message

railroad.cpp: In function 'Lint plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:69:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while( n < inc.size() ) n <<= 1;
              ^
railroad.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<inc.size();i++)
                  ^
railroad.cpp:80:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0,now=1;i<de.size();i++) {
                        ^

Subtask #1
11.0 / 11.0

#	결과	메모리	Grader output
1	Correct	37432 KB	n = 2
2	Correct	37432 KB	n = 2
3	Correct	37432 KB	n = 2
4	Correct	37432 KB	n = 2
5	Correct	37432 KB	n = 2
6	Correct	37432 KB	n = 2
7	Correct	37432 KB	n = 3
8	Correct	37432 KB	n = 3
9	Correct	37432 KB	n = 3
10	Correct	37432 KB	n = 8
11	Correct	37432 KB	n = 8
12	Correct	37432 KB	n = 8
13	Correct	37432 KB	n = 8
14	Correct	37432 KB	n = 8
15	Correct	37432 KB	n = 8
16	Correct	37432 KB	n = 8
17	Correct	37432 KB	n = 8
18	Correct	37432 KB	n = 8
19	Correct	37432 KB	n = 3
20	Correct	37432 KB	n = 7
21	Correct	37432 KB	n = 8
22	Correct	37432 KB	n = 8
23	Correct	37432 KB	n = 8
24	Correct	37432 KB	n = 8
25	Correct	37432 KB	n = 8

Subtask #2
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	37432 KB	n = 2
2	Correct	0 ms	37432 KB	n = 2
3	Correct	0 ms	37432 KB	n = 2
4	Correct	0 ms	37432 KB	n = 2
5	Correct	0 ms	37432 KB	n = 2
6	Correct	0 ms	37432 KB	n = 2
7	Correct	0 ms	37432 KB	n = 3
8	Correct	0 ms	37432 KB	n = 3
9	Correct	0 ms	37432 KB	n = 3
10	Correct	0 ms	37432 KB	n = 8
11	Correct	0 ms	37432 KB	n = 8
12	Correct	0 ms	37432 KB	n = 8
13	Correct	0 ms	37432 KB	n = 8
14	Correct	0 ms	37432 KB	n = 8
15	Correct	0 ms	37432 KB	n = 8
16	Correct	0 ms	37432 KB	n = 8
17	Correct	0 ms	37432 KB	n = 8
18	Correct	0 ms	37432 KB	n = 8
19	Correct	0 ms	37432 KB	n = 3
20	Correct	0 ms	37432 KB	n = 7
21	Correct	0 ms	37432 KB	n = 8
22	Correct	0 ms	37432 KB	n = 8
23	Correct	0 ms	37432 KB	n = 8
24	Correct	0 ms	37432 KB	n = 8
25	Correct	0 ms	37432 KB	n = 8
26	Correct	0 ms	37432 KB	n = 8
27	Correct	0 ms	37432 KB	n = 8
28	Correct	0 ms	37432 KB	n = 8
29	Correct	103 ms	37432 KB	n = 16
30	Correct	103 ms	37432 KB	n = 16
31	Correct	123 ms	37432 KB	n = 16
32	Correct	103 ms	37432 KB	n = 16
33	Correct	109 ms	37432 KB	n = 16
34	Correct	116 ms	37432 KB	n = 16
35	Correct	116 ms	37432 KB	n = 16
36	Correct	56 ms	37432 KB	n = 15
37	Correct	0 ms	37432 KB	n = 8
38	Correct	113 ms	37432 KB	n = 16
39	Correct	129 ms	37432 KB	n = 16
40	Correct	0 ms	37432 KB	n = 9
41	Correct	99 ms	37432 KB	n = 16
42	Correct	113 ms	37432 KB	n = 16
43	Correct	99 ms	37432 KB	n = 16
44	Correct	0 ms	37432 KB	n = 9
45	Correct	39 ms	37432 KB	n = 15
46	Correct	106 ms	37432 KB	n = 16
47	Correct	113 ms	37432 KB	n = 16
48	Correct	109 ms	37432 KB	n = 16

Subtask #3
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	45292 KB	n = 199999
2	Correct	173 ms	44784 KB	n = 199991
3	Correct	99 ms	45292 KB	n = 199993
4	Correct	119 ms	43140 KB	n = 152076
5	Incorrect	79 ms	40744 KB	answer is not correct: 1 instead of 0
6	Halted	0 ms	0 KB	-

Subtask #4
0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	37432 KB	n = 2
2	Correct	0 ms	37432 KB	n = 2
3	Correct	0 ms	37432 KB	n = 2
4	Correct	0 ms	37432 KB	n = 2
5	Correct	0 ms	37432 KB	n = 2
6	Correct	0 ms	37432 KB	n = 2
7	Correct	0 ms	37432 KB	n = 3
8	Correct	0 ms	37432 KB	n = 3
9	Correct	0 ms	37432 KB	n = 3
10	Correct	0 ms	37432 KB	n = 8
11	Correct	0 ms	37432 KB	n = 8
12	Correct	0 ms	37432 KB	n = 8
13	Correct	0 ms	37432 KB	n = 8
14	Correct	0 ms	37432 KB	n = 8
15	Correct	0 ms	37432 KB	n = 8
16	Correct	0 ms	37432 KB	n = 8
17	Correct	0 ms	37432 KB	n = 8
18	Correct	0 ms	37432 KB	n = 8
19	Correct	0 ms	37432 KB	n = 3
20	Correct	0 ms	37432 KB	n = 7
21	Correct	0 ms	37432 KB	n = 8
22	Correct	0 ms	37432 KB	n = 8
23	Correct	0 ms	37432 KB	n = 8
24	Correct	0 ms	37432 KB	n = 8
25	Correct	0 ms	37432 KB	n = 8
26	Correct	0 ms	37432 KB	n = 8
27	Correct	0 ms	37432 KB	n = 8
28	Correct	0 ms	37432 KB	n = 8
29	Correct	103 ms	37432 KB	n = 16
30	Correct	103 ms	37432 KB	n = 16
31	Correct	123 ms	37432 KB	n = 16
32	Correct	103 ms	37432 KB	n = 16
33	Correct	109 ms	37432 KB	n = 16
34	Correct	116 ms	37432 KB	n = 16
35	Correct	116 ms	37432 KB	n = 16
36	Correct	56 ms	37432 KB	n = 15
37	Correct	0 ms	37432 KB	n = 8
38	Correct	113 ms	37432 KB	n = 16
39	Correct	129 ms	37432 KB	n = 16
40	Correct	0 ms	37432 KB	n = 9
41	Correct	99 ms	37432 KB	n = 16
42	Correct	113 ms	37432 KB	n = 16
43	Correct	99 ms	37432 KB	n = 16
44	Correct	0 ms	37432 KB	n = 9
45	Correct	39 ms	37432 KB	n = 15
46	Correct	106 ms	37432 KB	n = 16
47	Correct	113 ms	37432 KB	n = 16
48	Correct	109 ms	37432 KB	n = 16
49	Correct	93 ms	45292 KB	n = 199999
50	Correct	173 ms	44784 KB	n = 199991
51	Correct	99 ms	45292 KB	n = 199993
52	Correct	119 ms	43140 KB	n = 152076
53	Incorrect	79 ms	40744 KB	answer is not correct: 1 instead of 0
54	Halted	0 ms	0 KB	-

답안 #32046

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 23.0 / 23.0

Subtask #3 0 / 30.0

Subtask #4 0 / 36.0

Subtask #1
11.0 / 11.0

Subtask #2
23.0 / 23.0

Subtask #3
0 / 30.0

Subtask #4
0 / 36.0