Submission #600604

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
600604	2022-07-21T06:09:32 Z	cheissmart	Shortcut (IOI16_shortcut)	C++14	Compilation error	0 ms	0 KB

shortcut

#include "shortcut.h"
#define int ll
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;
const ll oo = 1e18;

ll find_shortcut(int n, vi l, vi d, int c) {
    assert(SZ(l) == n - 1);
    assert(SZ(d) == n);
    V<ll> pos(n);
    for(int i = 1; i < n; i++)
        pos[i] = l[i - 1] + pos[i - 1];

    auto ok = [&] (ll k) {
        V<pair<ll, int>> a(n), b(n);
        for(int i = 0; i < n; i++) {
            a[i] = {pos[i] + d[i], i};
            b[i] = {k + pos[i] - d[i], i};
        }
        ll lb_sum = -oo, rb_sum = oo;
        ll lb_dif = -oo, rb_dif = oo;
        auto add_condition = [&] (int i, int j) {
            assert(i < j && pos[j] - pos[i] + d[i] + d[j] > k);
            // abs(x - pos[i]) + abs(y - pos[j]) <= k - (d[i] + d[j] + c)
            ll dd = k - (0LL + d[i] + d[j] + c);
            // pos[i] + pos[j] - d <= x + y <= pos[i] + pos[j] + d 
            // pos[i] - pos[j] - d <= x - y <= pos[i] - pos[j] + d 
            lb_sum = max(lb_sum, pos[i] + pos[j] - dd);
            rb_sum = min(rb_sum, pos[i] + pos[j] + dd);
            lb_dif = max(lb_dif, pos[i] - pos[j] - dd);
            rb_dif = min(rb_dif, pos[i] - pos[j] + dd);
        };
        function<void(int, int)> cdq = [&] (int l, int r) {
            if(r - l == 1) return;
            int m = (l + r) / 2;
            cdq(l, m), cdq(m, r);
            int mxj = -1, mnj = INF;
            for(int i = m - 1, j = r - 1; i >= l; i--) {
                while(j >= m && a[j].F > b[i].F) {
                    mxj = max(mxj, a[j].S);
                    mnj = min(mnj, a[j].S);
                    j--;
                }
                if(mxj != -1) {
                    add_condition(b[i].S, mnj);
                    add_condition(b[i].S, mxj);
                }
            }
            // b[i] < a[j]
            inplace_merge(a.begin() + l, a.begin() + m, a.begin() + r);
            inplace_merge(b.begin() + l, b.begin() + m, b.begin() + r);
        };
        cdq(0, n);
        if(lb_sum > rb_sum) return false;
        if(lb_dif > rb_dif) return false;
        for(int i = 0; i < n - 1; i++) {
            ll lb = max(lb_sum - pos[i], pos[i] - rb_dif), rb = min(rb_sum - pos[i], pos[i] - lb_dif);
            if(lb <= rb) {
                int j = lower_bound(pos.begin() + i + 1, pos.end(), lb) - pos.begin();
                if(j < n && pos[j] <= rb) {
                    return true;
                }
            }
        }
        return false;
    };

    ll lb = 1, rb = 1e15;
    while(lb <= rb) {
        ll mb = (lb + rb) / 2;
        if(ok(mb)) rb = mb - 1;
        else lb = mb + 1;
    }
    return lb;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from shortcut.cpp:3:
/usr/include/assert.h:70:20: error: expected ',' or '...' before '__line'
   70 |       unsigned int __line, const char *__function)
      |                    ^~~~~~
/usr/include/assert.h:74:13: error: variable or field '__assert_perror_fail' declared void
   74 | extern void __assert_perror_fail (int __errnum, const char *__file,
      |             ^~~~~~~~~~~~~~~~~~~~
shortcut.cpp:2:13: error: 'll' was not declared in this scope
    2 | #define int ll
      |             ^~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from shortcut.cpp:3:
/usr/include/assert.h:74:49: error: expected primary-expression before 'const'
   74 | extern void __assert_perror_fail (int __errnum, const char *__file,
      |                                                 ^~~~~
/usr/include/assert.h:75:7: error: expected primary-expression before 'unsigned'
   75 |       unsigned int __line, const char *__function)
      |       ^~~~~~~~
/usr/include/assert.h:75:28: error: expected primary-expression before 'const'
   75 |       unsigned int __line, const char *__function)
      |                            ^~~~~
shortcut.cpp:2:13: error: 'll' has not been declared
    2 | #define int ll
      |             ^~
In file included from /usr/include/ctype.h:26,
                 from /usr/include/c++/10/cctype:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:35,
                 from shortcut.cpp:3:
/usr/include/x86_64-linux-gnu/bits/types.h:32:28: error: expected initializer before '__u_short'
   32 | typedef unsigned short int __u_short;
      |                            ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:33:22: error: expected initializer before '__u_int'
   33 | typedef unsigned int __u_int;
      |                      ^~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:34:27: error: expected initializer before '__u_long'
   34 | typedef unsigned long int __u_long;
      |                           ^~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:39:26: error: expected initializer before '__int16_t'
   39 | typedef signed short int __int16_t;
      |                          ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:40:28: error: expected initializer before '__uint16_t'
   40 | typedef unsigned short int __uint16_t;
      |                            ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:41:20: error: expected initializer before '__int32_t'
   41 | typedef signed int __int32_t;
      |                    ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:42:22: error: expected initializer before '__uint32_t'
   42 | typedef unsigned int __uint32_t;
      |                      ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:44:25: error: expected initializer before '__int64_t'
   44 | typedef signed long int __int64_t;
      |                         ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:45:27: error: expected initializer before '__uint64_t'
   45 | typedef unsigned long int __uint64_t;
      |                           ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:54:9: error: '__int16_t' does not name a type; did you mean '__int8_t'?
   54 | typedef __int16_t __int_least16_t;
      |         ^~~~~~~~~
      |         __int8_t
/usr/include/x86_64-linux-gnu/bits/types.h:55:9: error: '__uint16_t' does not name a type; did you mean '__uint8_t'?
   55 | typedef __uint16_t __uint_least16_t;
      |         ^~~~~~~~~~
      |         __uint8_t
/usr/include/x86_64-linux-gnu/bits/types.h:56:9: error: '__int32_t' does not name a type; did you mean '__int8_t'?
   56 | typedef __int32_t __int_least32_t;
      |         ^~~~~~~~~
      |         __int8_t
/usr/include/x86_64-linux-gnu/bits/types.h:57:9: error: '__uint32_t' does not name a type; did you mean '__uint8_t'?
   57 | typedef __uint32_t __uint_least32_t;
      |         ^~~~~~~~~~
      |         __uint8_t
/usr/include/x86_64-linux-gnu/bits/types.h:58:9: error: '__int64_t' does not name a type; did you mean '__int8_t'?
   58 | typedef __int64_t __int_least64_t;
      |         ^~~~~~~~~
      |         __int8_t
/usr/include/x86_64-linux-gnu/bits/types.h:59:9: error: '__uint64_t' does not name a type; did you mean '__uint8_t'?
   59 | typedef __uint64_t __uint_least64_t;
      |         ^~~~~~~~~~
      |         __uint8_t
/usr/include/x86_64-linux-gnu/bits/types.h:63:18: error: expected initializer before '__quad_t'
   63 | typedef long int __quad_t;
      |                  ^~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:64:27: error: expected initializer before '__u_quad_t'
   64 | typedef unsigned long int __u_quad_t;
      |                           ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:72:18: error: expected initializer before '__intmax_t'
   72 | typedef long int __intmax_t;
      |                  ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:73:27: error: expected initializer before '__uintmax_t'
   73 | typedef unsigned long int __uintmax_t;
      |                           ^~~~~~~~~~~
In file included from /usr/include/ctype.h:26,
                 from /usr/include/c++/10/cctype:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:35,
                 from shortcut.cpp:3:
/usr/include/x86_64-linux-gnu/bits/types.h:145:25: error: expected initializer before '__dev_t'
  145 | __STD_TYPE __DEV_T_TYPE __dev_t; /* Type of device numbers.  */
      |                         ^~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:146:25: error: expected initializer before '__uid_t'
  146 | __STD_TYPE __UID_T_TYPE __uid_t; /* Type of user identifications.  */
      |                         ^~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:147:25: error: expected initializer before '__gid_t'
  147 | __STD_TYPE __GID_T_TYPE __gid_t; /* Type of group identifications.  */
      |                         ^~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:148:25: error: expected initializer before '__ino_t'
  148 | __STD_TYPE __INO_T_TYPE __ino_t; /* Type of file serial numbers.  */
      |                         ^~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:149:27: error: expected initializer before '__ino64_t'
  149 | __STD_TYPE __INO64_T_TYPE __ino64_t; /* Type of file serial numbers (LFS).*/
      |                           ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:150:26: error: expected initializer before '__mode_t'
  150 | __STD_TYPE __MODE_T_TYPE __mode_t; /* Type of file attribute bitmasks.  */
      |                          ^~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:151:27: error: expected initializer before '__nlink_t'
  151 | __STD_TYPE __NLINK_T_TYPE __nlink_t; /* Type of file link counts.  */
      |                           ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:152:25: error: expected initializer before '__off_t'
  152 | __STD_TYPE __OFF_T_TYPE __off_t; /* Type of file sizes and offsets.  */
      |                         ^~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:153:27: error: expected initializer before '__off64_t'
  153 | __STD_TYPE __OFF64_T_TYPE __off64_t; /* Type of file sizes and offsets (LFS).  */
      |                           ^~~~~~~~~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
In file included from /usr/include/ctype.h:26,
                 from /usr/include/c++/10/cctype:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:35,
                 from shortcut.cpp:3:
/usr/include/x86_64-linux-gnu/bits/types.h:156:27: error: expected initializer before '__clock_t'
  156 | __STD_TYPE __CLOCK_T_TYPE __clock_t; /* Type of CPU usage counts.  */
      |                           ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:157:26: error: expected initializer before '__rlim_t'
  157 | __STD_TYPE __RLIM_T_TYPE __rlim_t; /* Type for resource measurement.  */
      |                          ^~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:158:28: error: expected initializer before '__rlim64_t'
  158 | __STD_TYPE __RLIM64_T_TYPE __rlim64_t; /* Type for resource measurement (LFS).  */
      |                            ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:159:24: error: expected initializer before '__id_t'
  159 | __STD_TYPE __ID_T_TYPE __id_t;  /* General type for IDs.  */
      |                        ^~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:160:26: error: expected initializer before '__time_t'
  160 | __STD_TYPE __TIME_T_TYPE __time_t; /* Seconds since the Epoch.  */
      |                          ^~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:161:30: error: expected initializer before '__useconds_t'
  161 | __STD_TYPE __USECONDS_T_TYPE __useconds_t; /* Count of microseconds.  */
      |                              ^~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:162:31: error: expected initializer before '__suseconds_t'
  162 | __STD_TYPE __SUSECONDS_T_TYPE __suseconds_t; /* Signed count of microseconds.  */
      |                               ^~~~~~~~~~~~~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
In file included from /usr/include/ctype.h:26,
                 from /usr/include/c++/10/cctype:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:35,
                 from shortcut.cpp:3:
/usr/include/x86_64-linux-gnu/bits/types.h:174:29: error: expected initializer before '__blksize_t'
  174 | __STD_TYPE __BLKSIZE_T_TYPE __blksize_t;
      |                             ^~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:179:28: error: expected initializer before '__blkcnt_t'
  179 | __STD_TYPE __BLKCNT_T_TYPE __blkcnt_t;
      |                            ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:180:30: error: expected initializer before '__blkcnt64_t'
  180 | __STD_TYPE __BLKCNT64_T_TYPE __blkcnt64_t;
      |                              ^~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:183:30: error: expected initializer before '__fsblkcnt_t'
  183 | __STD_TYPE __FSBLKCNT_T_TYPE __fsblkcnt_t;
      |                              ^~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:184:32: error: expected initializer before '__fsblkcnt64_t'
  184 | __STD_TYPE __FSBLKCNT64_T_TYPE __fsblkcnt64_t;
      |                                ^~~~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:187:30: error: expected initializer before '__fsfilcnt_t'
  187 | __STD_TYPE __FSFILCNT_T_TYPE __fsfilcnt_t;
      |                              ^~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:188:32: error: expected initializer before '__fsfilcnt64_t'
  188 | __STD_TYPE __FSFILCNT64_T_TYPE __fsfilcnt64_t;
      |                                ^~~~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:191:28: error: expected initializer before '__fsword_t'
  191 | __STD_TYPE __FSWORD_T_TYPE __fsword_t;
      |                            ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:193:27: error: expected initializer before '__ssize_t'
  193 | __STD_TYPE __SSIZE_T_TYPE __ssize_t; /* Type of a byte count, or error.  */
      |                           ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:196:33: error: expected initializer before '__syscall_slong_t'
  196 | __STD_TYPE __SYSCALL_SLONG_TYPE __syscall_slong_t;
      |                                 ^~~~~~~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:198:33: error: expected initializer before '__syscall_ulong_t'
  198 | __STD_TYPE __SYSCALL_ULONG_TYPE __syscall_ulong_t;
      |                                 ^~~~~~~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:202:9: error: '__off64_t' does not name a type
  202 | typedef __off64_t __loff_t; /* Type of file sizes and offsets (LFS).  */
      |         ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:206:25: error: expected initializer before '__intptr_t'
  206 | __STD_TYPE __SWORD_TYPE __intptr_t;
      |                         ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:209:23: error: expected initializer before '__socklen_t'
  209 | __STD_TYPE __U32_TYPE __socklen_t;
      |                       ^~~~~~~~~~~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
In file included from /usr/include/c++/10/cctype:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:35,
                 from shortcut.cpp:3:
/usr/include/ctype.h:79:33: error: expected initializer before '*' token
   79 | extern const unsigned short int **__ctype_b_loc (void)
      |                                 ^
/usr/include/ctype.h:81:14: error: '__int32_t' does not name a type; did you mean '__int8_t'?
   81 | extern const __int32_t **__ctype_tolower_loc (void)
      |              ^~~~~~~~~
      |              __int8_t
/usr/include/ctype.h:83:14: error: '__int32_t' does not name a type; did you mean '__int8_t'?
   83 | extern const __int32_t **__ctype_toupper_loc (void)
      |              ^~~~~~~~~
      |              __int8_t
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: expected ';' at end of member declaration
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
shortcut.cpp:2:13: error: 'll' does not name a type
    2 | #define int ll
      |             ^~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:35,
                 from shortcut.cpp:3:
/usr/include/c++/10/cctype:64:11: error: 'isalnum' has not been declared in '::'
   64 |   using ::isalnum;
      |           ^~~~~~~
/usr/include/c++/10/cctype:65:11: error: 'isalpha' has not been declared in '::'
   65 |   using ::isalpha;
      |           ^~~~~~~
/usr/include/c++/10/cctype:66:11: error: 'iscntrl' has not been declared in '::'
   66 |   using ::iscntrl;
      |           ^~~~~~~
/usr/include/c++/10/cctype:67:11: error: 'isdigit' has not been declared in '::'
   67 |   using ::isdigit;
      |           ^~~~~~~
/usr/include/c++/10/cctype:68:11: error: 'isgraph' has not been declared in '::'
   68 |   using ::isgraph;
      |           ^~~~~~~
/usr/include/c++/10/cctype:69:11: error: 'islower' has not been declared in '::'
   69 |   using ::islower;
      |           ^~~~~~~
/usr/include/c++/10/cctype:70:11: error: 'isprint' has not been declared in '::'
   70 |   using ::isprint;