# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
125115 | 2019-07-04T16:03:47 Z | khulegub | Gondola (IOI14_gondola) | C++14 | 0 ms | 0 KB |
#include "gondola.h" #include <bits/stdc++.h> #define pb push_back #define mp make_pair #define xx first #define yy second using namespace std; typedef long long i64; typedef pair<int, int> pii; int valid(int n, int arr[]){ vector<pii> rep; vector<pii> v; for (int i = 0; i < n; i++){ arr[i]--; // cout << arr[i] << ' '; if (arr[i] >= n){ rep.pb(mp(arr[i] - n, i) ); } else v.pb(mp(i, arr[i]) ); } if(v.size() > 0){ int diff = v[0].yy - v[0].xx; int end = (n - 1) - diff; int diff2 = diff - n; // cout << diff2; int vn = v.size(); for (int i = 0; i < vn; i++){ if (v[i].xx <= end){ if (v[i].yy - v[i].xx != diff) return 0; } else{ if (v[i].yy - v[i].xx != diff2) return 0; } } } sort(rep.begin(), rep.end()); for(int i = 0; i + 1 < rep.size(); i++){ if(rep[i].xx == rep[i + 1].xx) return 0; } // cout << "veve"; return 1; } //---------------------- int replacement(int n, int arr[], int repl[]){ vector<pii> rep; vector<pii> v; for (int i = 0; i < n; i++){ arr[i]--; if (arr[i] >= n){ rep.pb( mp(arr[i] - n, i) ); } else { v.pb( mp(i, arr[i]) ); } } sort(rep.begin(), rep.end() ); if(v.size() > 0){ int diff = v[0].yy - v[0].xx; int end = (n - 1) - diff; int diff2 = diff - n; int repsz = 0; int last = 0; for(int i = 0; i < rep.size(); i++){ for(int j = last; j <= rep[i].xx; j++){ int tmp; if(j == last){ if(rep[i].yy <= end) tmp = rep[i].yy + diff; else tmp = rep[i].yy + diff2; } else{ tmp = n + j - 1; } tmp++; repl[j] = tmp; repsz++; } last = rep[i].xx + 1; } return repsz; // cout << diff2; } else{ //wtf evdreegu neg ch bdggu nasss int repsz = 0; int last = 0; for(int i = 0; i < rep.size(); i++){ for(int j = last; j <= rep[i].xx; j++){ int tmp; if(j == last){ tmp = rep[i].yy; } else{ tmp = n + j - 1; } tmp++; // cout << tmp << ' '; repl[j] = tmp; repsz++; } last = rep[i].xx + 1; } return repsz; } }