Submission #348938

#TimeUsernameProblemLanguageResultExecution timeMemory
348938talant117408Rail (IOI14_rail)C++17
100 / 100
96 ms4460 KiB
#include "rail.h" #ifndef EVAL #include "grader.cpp" #endif #pragma GCC optimize("Ofast") #include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //using namespace __gnu_pbds; using namespace std; //typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define precision(n) fixed << setprecision(n) #define pb push_back #define ub upper_bound #define lb lower_bound #define mp make_pair #define eps (double)1e-9 #define PI 2*acos(0.0) #define endl "\n" #define sz(v) int((v).size()) #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define OK cout << "OK" << endl; int occupied[1000007]; int d0[5003], d1[5003]; void findLocation(int n, int zeroth, int location[], int type[]){ int len = 2e9, ind = 0; for(int i = 1; i < n; i++){ d0[i] = getDistance(0, i); if(d0[i] < len){ len = d0[i]; ind = i; } } location[0] = zeroth; type[0] = occupied[zeroth] = 1; location[ind] = zeroth+len; type[ind] = occupied[zeroth+len] = 2; for(int i = 0; i < n; i++){ if(ind != i){ d1[i] = getDistance(ind, i); } } vector <pii> left, right; for(int i = 1; i < n; i++){ if(i != ind){ if(d0[i] == len+d1[i]){ if(len > d1[i]){ location[i] = location[ind]-d1[i]; type[i] = occupied[location[i]] = 1; } else{ left.pb(mp(d1[i], i)); } } else{ right.pb(mp(d0[i], i)); } } } sort(all(left)); sort(all(right)); int R = ind; for(auto a : right){ auto x = a.second; auto drx = getDistance(R, x); auto gap = (d0[R]+drx-d0[x])/2; if(occupied[location[R]-gap] == 1 || occupied[location[R]-gap] == 0){ location[x] = d0[x]+zeroth; type[x] = occupied[location[x]] = 2; R = x; } else{ location[x] = location[R]-drx; type[x] = occupied[location[x]] = 1; } } R = 0; for(auto a : left){ auto x = a.second; auto drx = getDistance(R, x); auto gap = (d1[R]+drx-d1[x])/2; if(occupied[location[R]+gap]%2 == 0){ location[x] = location[ind]-d1[x]; type[x] = occupied[location[x]] = 1; R = x; } else{ location[x] = location[R]+drx; type[x] = occupied[location[x]] = 2; } } } /* 4 6 1 4 2 5 2 10 1 1 1 0 2 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...