Submission #1272366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272366		thesen	Xylophone (JOI18_xylophone)	C++20	0 / 100	1 ms	412 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"
#define pb push_back
#define ll long long
#define vll vector <ll>
#define vbool vector<bool>
#define pairll pair<ll,ll>
#define fi first
#define sc second
#define rever greater<ll>()
using namespace std;

void solve(int n){
    ll en =n;
    ll a;
    ll l = 1, r = n-1, mid;
    while(l <r){
        if(l+1 == r){
            if(query(r, en) == n-1)l =r;
            break;
        }
        mid = (l+r)/2;
        if(query(mid, en) == n-1){
            l = mid;
        }else r = mid-1;
    }a = l;

    vll res(n+1); res[a]=1;
    vbool ans(n+1); ans[1] = true;
    if(a > 1){
        ll d = query(a-1, a);
        res[a-1] = d+1;
        ans[d+1]=true;
    }
    for(ll i = a-2; i > 0; i--){
        ll y = query(i, i+1);
        ll z = abs(res[i+1]-res[i+2]);

        if(res[i+1]+y > n){
            res[i] = res[i+1]-y;
            ans[res[i+1]-y] = true;
            continue;
        }else if(ans[res[i+1]+y]){
            res[i] = res[i+1]-y;
            ans[res[i+1]-y] = true;
            continue;
        }

        if(res[i+1]-y < 1){
            res[i] = res[i+1]+y;
            ans[res[i+1]+y] = true;
            continue;
        }else if(ans[res[i+1]-y]){
            res[i] = res[i+1]+y;
            ans[res[i+1]+y] = true;
            continue;
        }

        ll x = query(a-2, a);
        if(x == y+z){
            if(res[i+1] > res[i+2]){
                res[i] = res[i+1]+y;
                ans[res[i+1]+y] = true;
            }else{
                res[i] = res[i+1]-y;
                ans[res[i+1]-y] = true;
            }
        }else{
            if(res[i+1] > res[i+2]){
                res[i] = res[i+1]-y;
                ans[res[i+1]-y] = true;
            }else{
                res[i] = res[i+1]+y;
                ans[res[i+1]+y] = true;
            }
        }
    }

    res[a+1] = 1 + query(a, a+1);
    ans[1 + query(a, a+1)] = true;
    for(ll i = a+2; i <= n; i++){
        ll y = query(i-1, i);
        ll z = abs(res[i-1]-res[i-2]);

        if(res[i-1]+y > n){
            res[i] = res[i-1]-y;
            ans[res[i-1]-y] = true;
            continue;
        }else if(ans[res[i-1]+y]){
            res[i] = res[i-1]-y;
            ans[res[i-1]-y] = true;
            continue;
        }

        if(res[i-1]-y < 1){
            res[i] = res[i-1]+y;
            ans[res[i-1]+y] = true;
            continue;
        }else if(ans[res[i-1]-y]){
            res[i] = res[i-1]+y;
            ans[res[i-1]+y] = true;
            continue;
        }

        ll x = query(a, a+2);
        if(x == y+z){
            if(res[i-1] > res[i-2]){
                res[i] = res[i-1]+y;
                ans[res[i-1]+y] = true;
            }else{
                res[i] = res[i-1]-y;
                ans[res[i-1]-y] = true;
            }
        }else{
            if(res[i-1] > res[i-2]){
                res[i] = res[i-1]-y;
                ans[res[i-1]-y] = true;
            }else{
                res[i] = res[i-1]+y;
                ans[res[i-1]+y] = true;
            }
        }
    }

    for(ll i = 1; i <= n; i++)answer(i, res[i]);
    
}

// int main(){
//     ios::sync_with_stdio(false); cin.tie(nullptr);
//     ll t=1; //cin >> t;
//     for(int i = 1; i <= t; i++){
//         solve();
//     }
// }

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