Submission #433721

#	Time	Username	Problem	Language	Result	Execution time	Memory
433721		HediChehaidar	Xylophone (JOI18_xylophone)	C++17	0 / 100	0 ms	200 KiB

xylophone

/*
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){
   // 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){
    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 - 2;
    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--;
    }
  /*  for(int i = 0 ; i < ans ; i ++) {
        if(v[i] != res[i]) {
            cout << "wrong\n"; return;
        }
    }*/
    cur = ans2 + 1 ;
    while(cur < n){
        int q1 = query(cur  , cur + 1);
      //  cout << q1 << endl;
        if(res[cur - 1] - q1 < 1 || seen[res[cur - 1] - q1]){
            res[cur] = res[cur - 1] + q1;
          //  if(res[cur] > 5049) cout << "here" << endl;
        }
        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);
            //cout << cur << " " << q2 << endl;
            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;
        }
      //  cout << res[cur] << endl;
        seen[res[cur]] = true;
        if(res[cur] != v[cur]){
            cout << cur << " " << res[cur] << " " << v[cur] <<"\n";
            return;
        }
        cur++;
    }
    for(int i = 0 ; i < n ; i++) answer(i + 1 , res[i]);
  /*  for(int i = ans ; i < n ; i++){
        if(res[i] != v[i]) cout << "wrong2\n"; return;
    }*/
    //cout << "here" << endl;
}
/*int main(){
    //ifstream fin ("race.in");
    //ofstream fout ("race.out");
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int N = 5*1000;
    for(int i = 0 ; i < N ; i++){
        int x = i + 1;
        v.pb(x);
    }
    random_shuffle(all(v));
    int N; cin>>N;
    for(int i = 0 ; i < N ; i++) {
        int x; cin>>x;
        v.pb(x);
    }
    solve(N);
  //  for(auto c : res) cout << c << " " ; cout << "\n";
    for(int i = 0 ; i < n ; i++){
        if(res[i] != v[i]) return cout << "wrong\n",0;
    }
    cout << "ok\n";
    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 !
*/

• Subtask 1: 0 / 11
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53