제출 #433748

#제출 시각아이디문제언어결과실행 시간메모리
433748HediChehaidarXylophone (JOI18_xylophone)C++17
0 / 100
0 ms200 KiB
/* ID: hedichehaidar TASK: photo LANG: C++11 */ #include<bits/stdc++.h> #include "xylophone.h" typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef double db; ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD) ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM) #define ss second #define ff first #define all(x) (x).begin() , (x).end() #define pb push_back #define vi vector<int> #define vii vector<pair<int,int>> #define vl vector<ll> #define vll vector<pair<ll,ll>> #define pii pair<int,int> #define pll pair<ll,ll> #define pdd pair<double,double> #define vdd vector<pdd> #define dte tuple<double , double , double> using namespace std; const int INF = 1000*1000*1000; // 1 e 9 const int MOD = INF + 7; const double EPS = 0.000000001; // 1 e -9 const ll inf = (ll)1e18; int n; vi v; /*int query(int i , int j){ if(i > j || i < 1 || j > n) cout << "wrong3" << endl; // cout << i << " " << j << endl; int mn = INF, mx = -1; for(int x = i - 1 ; x <= j - 1 ; x++){ mn = min(mn , v[x]); mx = max(mx , v[x]); } return mx - mn; } int answer(int i , int a){ return 0; cout << i << " " << a << "\n"; }*/ bool seen[5050]; vi res; void solve(int N){ n = N; res.assign(n , 0); int l = 0 , r = n - 1; int ans = -1 , d = n - 1; while(l <= r){ int mid = (l + r) / 2 ; int q = query(1 , mid); if(q != d){ l = mid + 1; } else{ ans = mid; r = mid - 1; } } l = 0 ; r = ans; int ans2 = -1; while(l <= r){ int mid = (l+ r) / 2; int q = query(mid , ans); if(q != d){ r = mid - 1; } else{ ans2 = mid; l = mid + 1; } } swap(ans , ans2); res[ans - 1] = 1; res[ans2 - 1] = n; if(ans != 1) { res[ans - 2] = query(ans - 1 , ans) + 1; } if(ans2 != n){ res[ans2] = res[ans2 - 1] - query(ans2 , ans2 + 1); } if(ans != ans2 - 1){ res[ans] = query(ans , ans + 1) + 1; if(ans != ans2 - 2){ res[ans2 - 2] = res[ans2 - 1] - query(ans2 - 1 , ans2); } } for(auto c : res ) seen[c] = true; int cur = ans - 3; while(cur >= 0){ int q1 = query(cur + 1 , cur + 2); if(res[cur + 1] - q1 < 1 || seen[res[cur + 1] - q1]){ res[cur] = res[cur + 1] + q1; } else if(res[cur + 1] + q1 > n || seen[res[cur + 1] + q1]){ res[cur] = res[cur + 1] - q1; } else{ int q2 = query(cur + 1 , cur + 3); if(q1 == q2){ if(res[cur + 1] < res[cur + 2]){ res[cur] = res[cur + 1] + q1; } else res[cur] = res[cur + 1] - q1; } else if(q2 == abs(res[cur + 1] - res[cur + 2])){ if(res[cur + 1] < res[cur + 2]) res[cur] = res[cur + 1] + q1; else res[cur] = res[cur + 1] - q1; } else if(res[cur + 1] > res[cur + 2]) res[cur] = res[cur + 1] + q1; else res[cur] = res[cur + 1] - q1; } seen[res[cur]] = true; cur--; } cur = ans + 1 ; while(cur < ans2 - 2){ int q1 = query(cur , cur + 1); if(res[cur - 1] - q1 < 1 || seen[res[cur - 1] - q1]){ res[cur] = res[cur - 1] + q1; } else if(res[cur - 1] + q1 > n || seen[res[cur - 1] + q1]){ res[cur] = res[cur - 1] - q1; } else{ int q2 = query(cur - 1 , cur + 1); if(q1 == q2){ if(res[cur - 1] < res[cur - 2]){ res[cur] = res[cur - 1] + q1; } else res[cur] = res[cur - 1] - q1; } else if(q2 == abs(res[cur - 1] - res[cur - 2])){ if(res[cur - 1] < res[cur - 2]) res[cur] = res[cur - 1] + q1; else res[cur] = res[cur - 1] - q1; } else if(res[cur - 1] > res[cur - 2]) res[cur] = res[cur - 1] + q1; else res[cur] = res[cur - 1] - q1; } seen[res[cur]] = true; cur++; } cur = ans2 + 1; while(cur < n){ int q1 = query(cur , cur + 1); if(res[cur - 1] - q1 < 1 || seen[res[cur - 1] - q1]){ res[cur] = res[cur - 1] + q1; } else if(res[cur - 1] + q1 > n || seen[res[cur - 1] + q1]){ res[cur] = res[cur - 1] - q1; } else{ int q2 = query(cur - 1 , cur + 1); if(q1 == q2){ if(res[cur - 1] < res[cur - 2]){ res[cur] = res[cur - 1] + q1; } else res[cur] = res[cur - 1] - q1; } else if(q2 == abs(res[cur - 1] - res[cur - 2])){ if(res[cur - 1] < res[cur - 2]) res[cur] = res[cur - 1] + q1; else res[cur] = res[cur - 1] - q1; } else if(res[cur - 1] > res[cur - 2]) res[cur] = res[cur - 1] + q1; else res[cur] = res[cur - 1] - q1; } seen[res[cur]] = true; cur++; } for(int i = 0 ; i < n ; i++) answer(i + 1 , res[i]); } /*int main(){ //ifstream fin ("race.in"); //ofstream fout ("race.out"); ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int N = 5000; for(int i = 0 ; i < N ; i++){ int x = i + 1; v.pb(x); } random_shuffle(all(v)); // for(auto c : v) cout << c << " "; cout << "\n"; solve(N); //for(auto c : res) cout << c << " " ; cout << "\n\n"; for(int i = 0 ; i < n ; i++) if(v[i] != res[i]) return cout << "wrong1" << endl,0; return 0; }*/ /* Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO Read the statement CAREFULLY !! Make a GREADY APPROACH !!!! (start from highest / lowest) Make your own TESTS !! Be careful from CORNER CASES ! */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...