Submission #32044

#TimeUsernameProblemLanguageResultExecution timeMemory
32044osmanorhanRoller Coaster Railroad (IOI16_railroad)C++14
Compilation error
0 ms0 KiB
#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] ) return n; used[n] = 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( 0, now-s[i] ) ); } return dn[n][last] = ret; } Lint plan_roller_coaster(vector<int> S, vector<int> Ti) { s = S; ti = T; 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 ) ); 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 (stderr)

railroad.cpp: In function 'Lint f(int, int)':
railroad.cpp:38:13: error: incompatible types in assignment of 'int' to 'int [20]'
     used[n] = 1;
             ^
railroad.cpp:43:60: error: no matching function for call to 'max(int, Lint)'
             umin( ret, f( n|(1<<i), i ) + max( 0, now-s[i] ) );
                                                            ^
railroad.cpp:6:35: note: in definition of macro 'umin'
 #define umin( x, y ) x = min( x, (y) )
                                   ^
In file included from /usr/include/c++/5/vector:60:0,
                 from railroad.h:3,
                 from railroad.cpp:1:
/usr/include/c++/5/bits/stl_algobase.h:219:5: note: candidate: template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)
     max(const _Tp& __a, const _Tp& __b)
     ^
/usr/include/c++/5/bits/stl_algobase.h:219:5: note:   template argument deduction/substitution failed:
railroad.cpp:43:60: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'Lint {aka long long int}')
             umin( ret, f( n|(1<<i), i ) + max( 0, now-s[i] ) );
                                                            ^
railroad.cpp:6:35: note: in definition of macro 'umin'
 #define umin( x, y ) x = min( x, (y) )
                                   ^
In file included from /usr/include/c++/5/vector:60:0,
                 from railroad.h:3,
                 from railroad.cpp:1:
/usr/include/c++/5/bits/stl_algobase.h:265:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)
     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^
/usr/include/c++/5/bits/stl_algobase.h:265:5: note:   template argument deduction/substitution failed:
railroad.cpp:43:60: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'Lint {aka long long int}')
             umin( ret, f( n|(1<<i), i ) + max( 0, now-s[i] ) );
                                                            ^
railroad.cpp:6:35: note: in definition of macro 'umin'
 #define umin( x, y ) x = min( x, (y) )
                                   ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:64,
                 from railroad.cpp:2:
/usr/include/c++/5/bits/stl_algo.h:3457:5: note: candidate: template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)
     max(initializer_list<_Tp> __l)
     ^
/usr/include/c++/5/bits/stl_algo.h:3457:5: note:   template argument deduction/substitution failed:
railroad.cpp:43:60: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
             umin( ret, f( n|(1<<i), i ) + max( 0, now-s[i] ) );
                                                            ^
railroad.cpp:6:35: note: in definition of macro 'umin'
 #define umin( x, y ) x = min( x, (y) )
                                   ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:64,
                 from railroad.cpp:2:
/usr/include/c++/5/bits/stl_algo.h:3463:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)
     max(initializer_list<_Tp> __l, _Compare __comp)
     ^
/usr/include/c++/5/bits/stl_algo.h:3463:5: note:   template argument deduction/substitution failed:
railroad.cpp:43:60: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
             umin( ret, f( n|(1<<i), i ) + max( 0, now-s[i] ) );
                                                            ^
railroad.cpp:6:35: note: in definition of macro 'umin'
 #define umin( x, y ) x = min( x, (y) )
                                   ^
railroad.cpp: In function 'Lint plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:50:10: error: 'T' was not declared in this scope
     ti = T;
          ^
railroad.cpp:66:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while( n < inc.size() ) n <<= 1;
              ^
railroad.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<inc.size();i++)
                  ^
railroad.cpp:77:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0,now=1;i<de.size();i++) {
                        ^