Submission #433773

#	Time	Username	Problem	Language	Result	Execution time	Memory
433773		HediChehaidar	Xylophone (JOI18_xylophone)	C++17	0 / 100	3 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;
    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;
}
void answer(int i , int a){
    res[i - 1] = a;
}*/
vi res;
bool seen[5050];
void solve(int N){
    n = N;
    res.assign(n , 0);
    if(n == 2){
        answer(1 , 1);
        answer(2 , 2);
        return;
    }
    if(n == 3){
        if(query(2 , 3) == 1){
            answer(1 , 1);
            if(query(1 , 2) == 1){
                answer(2 , 2);
                answer(3 , 3);
            }
            else{
                answer(2 , 3);
                answer(3 , 2);
            }
        }
        else{
            answer(1 , 2); answer(2 , 1); answer(3 , 3);
        }
        return;
    }
    int l = 1 , r = n;
    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 ; cin>>N;
    for(int i = 0 ; i < N ; i++){
        int x ; cin>>x;
        v.pb(x);
    }
   // random_shuffle(all(v));
    bool b = false;
    for(int i = 0 ; i < N ; i++){
        if(!b && v[i] == N) return cout << "wrong2" << endl,0;
        if(v[i] == 1) break;
    }
   //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 !
*/

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