제출 #392716

#제출 시각아이디문제언어결과실행 시간메모리
392716usachevd0Shortcut (IOI16_shortcut)C++17
0 / 100
1 ms460 KiB
#pragma gcc optimize("Ofast") #pragma gcc optimize("O3") #pragma gcc optimize("no-stack-protector") #pragma gcc optimize("unroll-loops") #pragma gcc optimize("fast-math") #pragma gcc target("avx,avx2,sse,sse2,sse3,ssse3,sse4,ffa") #include <iostream> #include <fstream> #include <iomanip> #include <vector> #include <cstdio> #include <cstring> #include <algorithm> #include <numeric> #ifndef DEBUG #include "shortcut.h" #endif using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using ld = long double; /*template<typename T1, typename T2> bool chkmin(T1& x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1& x, T2 y) { return y > x ? (x = y, true) : false; }*/ void chkmin(ll& x, ll y) { if (y < x) { x = y; } } void chkmax(ll& x, ll y) { if (y > x) { x = y; } } void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) { cerr << a[i] << ' '; } cerr << endl; } #ifdef DEBUG #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n) #else #define debug(...) 1337 #define mdebug(a, n) 1337 #endif template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) { for (auto& x : v) { stream << x << ' '; } return stream; } template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; } const ll inf64 = 4e3 * 1e9; const int maxN = 3003; int n, c; //ll sum_lo[maxN][maxN], sum_hi[maxN][maxN]; //ll dif_lo[maxN][maxN], dif_hi[maxN][maxN]; ll sum_lo_f[maxN][maxN], sum_hi_f[maxN][maxN]; ll dif_lo_f[maxN][maxN], dif_hi_f[maxN][maxN]; ll naive[maxN][maxN]; ll x[maxN], d[maxN]; bool good(ll D) { ll slo = -inf64, shi = +inf64; ll dlo = -inf64, dhi = +inf64; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (naive[i][j] > D) { if (D < d[i] + d[j] + c) { return false; } chkmin(slo, sum_lo_f[i][j] - D); chkmax(shi, sum_hi_f[i][j] + D); chkmin(dlo, dif_lo_f[i][j] - D); chkmax(dhi, dif_hi_f[i][j] + D); /*sum_lo[i][j] = sum_lo_f[i][j] - D; sum_hi[i][j] = sum_hi_f[i][j] + D; dif_lo[i][j] = dif_lo_f[i][j] - D; dif_hi[i][j] = dif_hi_f[i][j] + D;*/ } else { /*sum_lo[i][j] = dif_lo[i][j] = -inf64; sum_hi[i][j] = dif_hi[i][j] = +inf64;*/ } } } /*for (int i = 0; i < n; ++i) { ll cur = -inf64; for (int j = n - 1; j >= 0; --j) { chkmax(cur, sum_lo[i][j]); sum_lo[i][j] = cur; } cur = +inf64; for (int j = 0; j < n; ++j) { chkmin(cur, sum_hi[i][j]); sum_hi[i][j] = cur; } cur = -inf64; for (int j = n - 1; j >= 0; --j) { chkmax(cur, dif_lo[i][j]); dif_lo[i][j] = cur; } cur = +inf64; for (int j = 0; j < n; ++j) { chkmin(cur, dif_hi[i][j]); dif_hi[i][j] = cur; } } for (int j = 0; j < n; ++j) { ll cur = -inf64; for (int i = n - 1; i >= 0; --i) { chkmax(cur, sum_lo[i][j]); sum_lo[i][j] = cur; } cur = +inf64; for (int i = 0; i < n; ++i) { chkmin(cur, sum_hi[i][j]); sum_hi[i][j] = cur; } cur = -inf64; for (int i = 0; i < n; ++i) { chkmax(cur, dif_lo[i][j]); dif_lo[i][j] = cur; } cur = +inf64; for (int i = n - 1; i >= 0; --i) { chkmin(cur, dif_hi[i][j]); dif_hi[i][j] = cur; } }*/ if (slo > shi || dlo > dhi) return false; /*for (int i = n - 1; i >= 0; --i) { for (int j = n - 1; j > i; --j) { chkmax(sum_lo[i][j], sum_lo[i + 1][j]); chkmax(sum_lo[i][j], sum_lo[i][j + 1]); } for (int j = i + 1; j < n; ++j) { chkmin(dif_hi[i][j], dif_hi[i + 1][j]); chkmin(dif_hi[i][j], dif_hi[i][j - 1]); } } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (i > 0) chkmin(sum_hi[i][j], sum_hi[i - 1][j]); chkmin(sum_hi[i][j], sum_hi[i][j - 1]); } for (int j = n - 1; j > i; --j) { if (i > 0) chkmax(dif_lo[i][j], dif_lo[i - 1][j]); chkmax(dif_lo[i][j], dif_lo[i][j + 1]); } }*/ for (int l = 0; l < n; ++l) { for (int r = l + 1; r < n; ++r) { ll sum = x[l] + x[r]; ll dif = x[r] - x[l]; /*if (l == 1 && r == 3) { debug(sum, dif); debug(sum_lo[l][r], sum_hi[l][r]); debug(dif_lo[l][r], dif_hi[l][r]); }*/ //if (sum_lo[l][r] <= sum && sum <= sum_hi[l][r] && // dif_lo[l][r] <= dif && dif <= dif_hi[l][r]) if (slo <= sum && sum <= shi && dlo <= dif && dif <= dhi) { return true; } } } return false; } ll find_shortcut(int _n, vector<int> dx, vector<int> _d, int _c) { n = _n; c = _c; for (int i = 0; i < n; ++i) d[i] = _d[i]; for (int i = 0; i + 1 < n; ++i) { x[i + 1] = x[i] + dx[i]; } int maxd1 = -1e9, maxd2 = -1e9; for (int i = 0; i < n; ++i) { if (d[i] >= maxd1) { maxd2 = maxd1; maxd1 = d[i]; } else if (d[i] > maxd2) { maxd2 = d[i]; } } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { naive[i][j] = d[i] + d[j] + x[j] - x[i]; sum_lo_f[i][j] = x[i] + x[j] + d[i] + d[j] + c; sum_hi_f[i][j] = x[i] + x[j] - d[i] - d[j] - c; dif_lo_f[i][j] = d[i] + d[j] + c - x[i] + x[j]; dif_hi_f[i][j] = -d[i] - d[j] - c + x[j] - x[i]; } } /*for (int i = 0; i <= n; ++i) { fill(sum_lo[i], sum_lo[i] + n + 1, -inf64); fill(sum_hi[i], sum_hi[i] + n + 1, +inf64); fill(dif_lo[i], dif_lo[i] + n + 1, -inf64); fill(dif_hi[i], dif_hi[i] + n + 1, +inf64); }*/ ll vl = maxd1 + maxd2; ll vr = maxd1 + maxd2 + x[n - 1]; while (vr - vl > 1) { ll vm; if (0 && vr - vl > 10) { vm = vl + (vr - vl) * 0.575; } else { vm = (vl + vr) >> 1; } if (good(vm)) { vr = vm; } else { vl = vm; } } return vr; } #ifdef DEBUG int32_t main() { #ifdef DEBUG freopen("in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); int n, c; cin >> n >> c; vector<int> l(n - 1), d(n); for (int& x : l) cin >> x; for (int& x : d) cin >> x; cout << find_shortcut(n, l, d, c) << '\n'; return 0; } #endif

컴파일 시 표준 에러 (stderr) 메시지

shortcut.cpp:1: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    1 | #pragma gcc optimize("Ofast")
      | 
shortcut.cpp:2: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    2 | #pragma gcc optimize("O3")
      | 
shortcut.cpp:3: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    3 | #pragma gcc optimize("no-stack-protector")
      | 
shortcut.cpp:4: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    4 | #pragma gcc optimize("unroll-loops")
      | 
shortcut.cpp:5: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    5 | #pragma gcc optimize("fast-math")
      | 
shortcut.cpp:6: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
    6 | #pragma gcc target("avx,avx2,sse,sse2,sse3,ssse3,sse4,ffa")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...