Submission #1210152

#TimeUsernameProblemLanguageResultExecution timeMemory
1210152sanoShortcut (IOI16_shortcut)C++20
71 / 100
2095 ms1984 KiB
//#include "shortcut.h" #include<iostream> #include<vector> #include<queue> #include<deque> #include<string> #include<fstream> #include<algorithm> #include <iomanip> #include<map> #include <set> #include <unordered_map> #include <stack> #include <unordered_set> #include <cmath> #include <cstdint> #include <cassert> #include <bitset> #include <random> #include <chrono> #include <cstring> #define shit short int #define ll long long #define ld long double //#define int ll #define For(i, n) for(int i = 0; i < (int)n; i++) #define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++) #define rfor(i, n) for(int i = (int)n; i >= (int)0; i--) #define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--) #define vec vector #define ff first #define ss second #define pb push_back #define pii pair<ll, ll> #define pld pair<ld, ld> #define NEK 2000000000000000 #define mod 1000000007 #define mod2 1000000009 #define rsz resize #define prv 43 #define prv2 47 #define D 8 #define trav(a,x) for (auto& a: x) #define pb push_back #define ub upper_bound #define lb lower_bound #define all(x) (x).begin(), (x).end() #define sig 0.0000001 using namespace std; bool check(ll mid, vec<ll>& d, vec<ll>& ps, ll c) { int n = d.size(); ll pp = (-2) * NEK, pm = (-2) * NEK, mp = (-2) * NEK, mm = (-2) * NEK; For(i, n) { ffor(j, i + 1, n) { if (ps[j] - ps[i] + d[i] + d[j] <= mid) continue; ll mojko = mid - d[i] - d[j] - c; //(ps[i] - y) + (ps[j] - z) <= mojko //ps[i] + ps[j] - mojko <= y+z pp = max(pp, ps[i] + ps[j] - mojko); //ps[i] - ps[j] - mojko <= y - z pm = max(pm, ps[i] - ps[j] - mojko); //ps[j] - ps[i] - mojko <= z - y mp = max(mp, ps[j] - ps[i] - mojko); //-ps[i] - ps[j] - mojko <= - z - y mm = max(mm, -ps[i] - ps[j] - mojko); } } For(i, n) { ffor(j, i + 1, n) { if (ps[i] + ps[j] >= pp && ps[i] - ps[j] >= pm && ps[j] - ps[i] >= mp && -ps[i] - ps[j] >= mm) { return 1; } } } return 0; } ll find_shortcut(int n1, vec<int> len, vec<int> d1, int c1) { ll n = n1; ll c = c1; vec<ll> d; For(i, d1.size()) d.push_back(d1[i]); vec<ll> ps(n); ps[0] = 0; For(i, (n - 1)) { ps[i + 1] = ps[i] + len[i]; } ll l = 0, r = NEK; while (l < r) { ll mid = (l + r) / 2; if (check(mid, d, ps, c)) r = mid; else l = mid + 1; } return l; } /* signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, c; while (1) { //cin >> n >> c; n = 10; c = rand() % 10; vec<int> l(n - 1), d(n); For(i, (n - 1)) { //cin >> l[i]; l[i] = rand() % 10; } For(i, n) { //cin >> d[i]; d[i] = rand() % 10; } ll odp1 = find_shortcut_pomale(n, l, d, c); ll odp2 = find_shortcut(n, l, d, c); if (odp1 != odp2) { odp1 = find_shortcut_pomale(n, l, d, c); odp2 = find_shortcut(n, l, d, c); } cout << odp2 << '\n'; //return 0; } return 0; }*/

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...