Submission #320406

#TimeUsernameProblemLanguageResultExecution timeMemory
320406VROOM_VARUNShortcut (IOI16_shortcut)C++14
0 / 100
2090 ms384 KiB
/* ID: varunra2 LANG: C++ TASK: shortcut */ #include <bits/stdc++.h> #include "shortcut.h" using namespace std; #ifdef DEBUG #include "lib/debug.h" #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define debug_arr(...) \ cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__) #pragma GCC diagnostic ignored "-Wsign-compare" //#pragma GCC diagnostic ignored "-Wunused-parameter" //#pragma GCC diagnostic ignored "-Wunused-variable" #else #define debug(...) 42 #endif #define int long long #define EPS 1e-9 #define IN(A, B, C) assert(B <= A && A <= C) #define INF (int)1e3 #define MEM(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define MP make_pair #define PB push_back #define all(cont) cont.begin(), cont.end() #define rall(cont) cont.end(), cont.begin() #define x first #define y second const double PI = acos(-1.0); typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef map<int, int> MPII; typedef multiset<int> MSETI; typedef set<int> SETI; typedef set<string> SETS; typedef vector<int> VI; typedef vector<PII> VII; typedef vector<VI> VVI; typedef vector<string> VS; #define rep(i, a, b) for (int i = a; i < (b); ++i) #define trav(a, x) for (auto& a : x) #define sz(x) (int)(x).size() typedef pair<int, int> pii; typedef vector<int> vi; #pragma GCC diagnostic ignored "-Wsign-compare" // util functions VI l; VI x; VI d; VII ord; vector<bool> dom; VI doms; int n; int c; void cop(VI& a, vector<int32_t> b) { a.resize(sz(b)); for (int i = 0; i < sz(a); i++) { a[i] = b[i]; } } void genPref() { x.resize(n); x[0] = 0ll; for (int i = 1; i < n; i++) { x[i] = x[i - 1] + l[i - 1]; } } void genDom() { // here we need to generate statinos that are not dominated by anybody // then x[dom[i]] + d[dom[i]] is non decreasing dom.assign(n, true); // to do this, we need to generate prefix and suffix maxima of stuff lol int mx = -INF; for (int i = 0; i < n; i++) { int cur = d[i] + x[i]; mx = max(mx, cur); if (cur < mx) dom[i] = false; } mx = -INF; for (int i = n - 1; i >= 0; i--) { int cur = d[i] - x[i]; mx = max(mx, cur); if (cur < mx) dom[i] = false; } for (int i = 0; i < n; i++) { if (dom[i]) doms.PB(i); } assert(!doms.empty()); } void genOrd() { // we also need to generate a sorted vector of pairs that contains when the // ith element is introduced, and its index ord.resize(n); for (int i = 0; i < n; i++) { ord[i] = MP(x[i] - d[i], i); } sort(all(ord)); } int mnsum, mxsum, mndif, mxdif; void upd(int i) { int x = ::x[i], d = ::d[i]; int sum = x + d, dif = x - d; mnsum = min(mnsum, sum); mxsum = max(mxsum, sum); mndif = min(mndif, dif); mxdif = max(mxdif, dif); } const int bad = 92; void initsumdif() { mnsum = INF; mxsum = -INF; mndif = INF; mxdif = -INF; } bool works(int k) { VI vals = {INF, -INF, INF, -INF}; initsumdif(); int p1 = 0; // for (int i = 0; i < n; i++) { // if (dom[i] == false) continue; // while (p1 < n and (ord[p1].x < x[i] + d[i] - k and ord[p1].y <= i)) { // // now we process it // upd(p1); // p1++; // } // int sum = x[i] + d[i], dif = x[i] - d[i]; // vals[0] = min(vals[0], (k - c) + dif + mndif); // vals[1] = max(vals[1], sum + mxsum - (k - c)); // vals[2] = min(vals[2], (k - c) + dif - mxsum); // vals[3] = max(vals[3], sum - mndif - (k - c)); // } for(int i = 0; i < n; i++) { initsumdif(); for(int j = 0; j < i; j++) { if(x[i] + d[i] - (x[j] - d[j]) > k) upd(j); } int sum = x[i] + d[i], dif = x[i] - d[i]; vals[0] = min(vals[0], (k - c) + dif + mndif); vals[1] = max(vals[1], sum + mxsum - (k - c)); vals[2] = min(vals[2], (k - c) + dif - mxsum); vals[3] = max(vals[3], sum - mndif - (k - c)); } // now we need to find two points in the rectangle defined by vals int maxsum, minsum, maxdif, mindif; maxsum = vals[0]; minsum = vals[1]; maxdif = vals[2]; mindif = vals[3]; debug(maxsum, minsum, maxdif, mindif, k); int curdif = 0; int cursum = n; if (maxsum < minsum or maxdif < mindif) return 0; for (int i = 0; i < n; i++) { while (curdif < n and x[curdif] - x[i] < mindif) curdif++; while (cursum > 0 and x[cursum - 1] + x[i] >= minsum) cursum--; int cur = max({cursum, curdif, i + 1}); if (cur < n and x[cur] + x[i] <= maxsum and x[cur] - x[i] <= maxdif) return true; } // for(int i = 0; i < n; i++) { // for(int j = 0; j < i; j++) { // int sum = x[i] + x[j]; // int dif = x[i] - x[j]; // if(sum >= minsum and sum <= maxsum and dif >= mindif and dif <= maxdif) // return true; // } // } return false; } ll find_shortcut(int32_t _n, vector<int32_t> _l, vector<int32_t> _d, int32_t _c) { n = _n; c = _c; cop(l, _l); cop(d, _d); genPref(); genDom(); genOrd(); // debug(dom); debug(doms); debug(ord); int xx = -1; int z = INF; for (int b = z; b >= 1; b /= 2) { while (!works(xx + b)) xx += b; } return xx + 1; } // int32_t main() { // #ifndef ONLINE_JUDGE // freopen("shortcut.in", "r", stdin); // freopen("shortcut.out", "w", stdout); // #endif // cin.sync_with_stdio(0); // cin.tie(0); // int n, c; // cin >> n >> c; // vector<int32_t> l(n - 1); // vector<int32_t> d(n); // for (int i = 0; i < n - 1; i++) { // cin >> l[i]; // } // for (int i = 0; i < n; i++) { // cin >> d[i]; // } // cout << find_shortcut(n, l, d, c) << '\n'; // return 0; // }

Compilation message (stderr)

shortcut.cpp: In function 'bool works(long long int)':
shortcut.cpp:20:20: warning: statement has no effect [-Wunused-value]
   20 | #define debug(...) 42
      |                    ^~
shortcut.cpp:171:3: note: in expansion of macro 'debug'
  171 |   debug(maxsum, minsum, maxdif, mindif, k);
      |   ^~~~~
shortcut.cpp:138:7: warning: unused variable 'p1' [-Wunused-variable]
  138 |   int p1 = 0;
      |       ^~
shortcut.cpp: In function 'll find_shortcut(int32_t, std::vector<int>, std::vector<int>, int32_t)':
shortcut.cpp:20:20: warning: statement has no effect [-Wunused-value]
   20 | #define debug(...) 42
      |                    ^~
shortcut.cpp:203:3: note: in expansion of macro 'debug'
  203 |   debug(doms);
      |   ^~~~~
shortcut.cpp:20:20: warning: statement has no effect [-Wunused-value]
   20 | #define debug(...) 42
      |                    ^~
shortcut.cpp:204:3: note: in expansion of macro 'debug'
  204 |   debug(ord);
      |   ^~~~~
#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...