Submission #590473

#	Time	Username	Problem	Language	Result	Execution time	Memory
590473		tamthegod	Xylophone (JOI18_xylophone)	C++14	47 / 100	87 ms	312 KiB

xylophone

#include<bits/stdc++.h>
#include "xylophone.h"

#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 5000 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int res[maxN];
int random(int l, int r)
{
    return l + (rng() % (r - l + 1));
}
void solve(int n)
{
    int low = 1, high = n, mid;
    while(low <= high)
    {
        mid = (low + high) / 2;
        if(query(mid, n) == n - 1) low = mid + 1;
        else high = mid -1;
    }
    low--;
    res[low] = 1;
    //cout << query(1, 2);exit(0);
    if(low > 1)
    {
        res[low - 1] = 1 + query(low - 1, low);
    }
    if(low < n) res[low + 1] = 1 + query(low, low + 1);
    for(int i=low-2; i>=1; i--)
    {
        int val1 = query(i, i + 1);
        if(res[i + 1] + val1 > n)
        {
            res[i] = res[i + 1] - val1;
            continue;
        }
        if(res[i + 1] - val1 < 1)
        {
            res[i] = res[i + 1] + val1;
            continue;
        }
        int val2 = query(i, i + 2);
        if(res[i + 1] > res[i + 2])
        {
            if(res[i + 1] - res[i + 2] == val2)
            {
                res[i] = res[i + 1] - val1;
            }
            else
            {
                int val = res[i + 2] + val2;
                if(val - res[i + 1] == val1) res[i] = val;
                else res[i] = res[i + 1] - val2;
            }
        }
        else
        {
            if(res[i + 2] - res[i + 1] == val2)
            {
                res[i] = res[i + 1] + val1;
            }
            else
            {
                int val = res[i + 2] - val2;
                if(res[i + 1] - val == val1) res[i] = val;
                else res[i] = res[i + 1] + val2;
            }
        }
    }
    for(int i=low+2; i<=n; i++)
    {
        int val1 = query(i - 1, i);
        if(res[i - 1] + val1 > n)
        {
            res[i] = res[i - 1] - val1;
            continue;
        }
        if(res[i - 1] - val1 < 1)
        {
            res[i] = res[i - 1] + val1;
            continue;
        }
        int val2 = query(i - 2, i);
        if(res[i - 1] > res[i - 2])
        {
            if(res[i - 1] - res[i - 2] == val2)
            {
                res[i] = res[i - 1] - val1;
            }
            else
            {
                int val = res[i - 2] + val2;
                if(val - res[i - 1] == val1) res[i] = val;
                else res[i] = res[i - 1] - val2;
            }
        }
        else
        {
            if(res[i - 2] - res[i - 1] == val2)
            {
                res[i] = res[i - 1] + val1;
            }
            else
            {
                int val = res[i - 2] - val2;
                if(res[i - 1] - val == val1) res[i] = val;
                else res[i] = res[i - 1] + val2;
            }
        }
    }
    for(int i=1; i<=n; i++) answer(i, res[i]);
}

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