Submission #1058091

#TimeUsernameProblemLanguageResultExecution timeMemory
1058091Zbyszek99Circle Passing (EGOI24_circlepassing)C++17
20 / 100
425 ms1048580 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define size(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace std; //mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll rand(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; int n,m,q; int dist(int a,int b) { return min(abs(a-b),2*n-abs(a-b)); } bool* best; int* right_; int* left_; bool* best2; int* right_2; int* left_2; void solve() { cin >> n >> m >> q; best = new bool[n]; right_ = new int[n]; left_ = new int[n]; best2 = new bool[n]; right_2 = new int[n]; left_2 = new int[n]; rep(i,n) best[i] = false; rep(i,n) best2[i] = false; rep(i,m) { int a; cin >> a; best[a] = true; best2[a] = true; } int pop = -1; int cur_i = 0; rep(i,n*3) { if(cur_i < n) { if(best[cur_i]) pop = cur_i; left_[cur_i] = pop; } else { if(best2[cur_i-n]) pop = cur_i; left_2[cur_i-n] = pop; } cur_i++; if(cur_i == 2*n) cur_i = 0; } pop = -1; cur_i = n-1; for(int i = n*3-1; i>=0;i--) { // cout << cur_i << " " << pop << " right\n"; if(cur_i < n) { if(best[cur_i]) pop = cur_i; right_[cur_i] = pop; } else { if(best2[cur_i-n]) pop = cur_i; right_2[cur_i-n] = pop; } cur_i--; if(cur_i == -1) cur_i = n*2-1; } rep(i,q) { int a,b; cin >> a >> b; if(a > b) swap(a,b); int l = 0; int r = 0; if(a < n) { l = left_[a]; r = right_[a]; } else { l = left_2[a-n]; r = right_2[a-n]; } int m1 = dist(a,b); int m2 = left_[a] == -1 ? 1e9 : dist(a,l) + dist((l+n) % (n*2),b)+1; int m3 = right_[a] == -1 ? 1e9 : dist(a,r) + dist((r+n) % (n*2),b)+1; // cout << m1 << " " << m2 << " " << m3 << " " << l << " " << r << " m\n"; cout << min(min(m1,m2),m3) << "\n"; } } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random(); int t = 1; // cin >> t; while(t--) solve(); }
#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...