Submission #590482

#	Time	Username	Problem	Language	Result	Execution time	Memory
590482		Tien_Noob	Xylophone (JOI18_xylophone)	C++17	100 / 100	76 ms	424 KiB

xylophone

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#include <xylophone.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 5e3;
int res[N + 1];
bool exist[N + 1];
void solve(int n)
{
    int low = 1, high = n;
    while(low <= high)
    {
        int mid = (low + high)/2;
        if (query(mid, n) == n - 1)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    res[high] = 1;
    exist[1] = true;
    if (high < n)
    {
        res[high + 1] = 1 + query(high, high + 1);
        exist[res[high + 1]] = true;
        for (int i = high + 2; i <= n; ++ i)
        {
            int b = query(i - 1, i);
            if (res[i - 1] + b > n || exist[res[i - 1] + b])
            {
                res[i] = res[i - 1] - b;
                exist[res[i]] = true;
                continue;
            }
            if (res[i - 1] - b < 1 || exist[res[i - 1] - b])
            {
                res[i] = res[i - 1] + b;
                exist[res[i]] = true;
                continue;
            }
            int a = query(i - 2, i);
            if (res[i - 1] > res[i - 2])
            {
                if (res[i - 1] + b == a + res[i - 2])
                {
                    res[i] = res[i - 1] + b;
                }
                else
                {
                    res[i] = res[i - 1] - b;
                }
            }
            else
            {
                if (res[i - 2] - a == res[i - 1] - b)
                {
                    res[i] = res[i - 1] - b;
                }
                else
                {
                    res[i] = res[i - 1] + b;
                }
            }
            exist[res[i]] = true;
        }
    }
    if (high > 1)
    {
        res[high - 1] = 1 + query(high - 1, high);
        exist[res[high - 1]] = true;
        for (int i = high - 2; i >= 1; -- i)
        {
            int b = query(i, i + 1);
            if (res[i + 1] + b > n || exist[res[i + 1] + b])
            {
                res[i] = res[i + 1] - b;
                exist[res[i]] = true;
                continue;
            }
            if (res[i + 1] - b < 1 || exist[res[i + 1] - b])
            {
                res[i] = res[i + 1] + b;
                exist[res[i]] = true;
                continue;
            }
            int a = query(i, i + 2);
            if (res[i + 2] > res[i + 1])
            {
                if (res[i + 1] - b == res[i + 2] - a)
                {
                    res[i] = res[i + 1] - b;
                }
                else
                {
                    res[i] = res[i + 1] + b;
                }
            }
            else
            {
                if (res[i + 1] + b == res[i + 2] + a)
                {
                    res[i] = res[i + 1] + b;
                }
                else
                {
                    res[i] = res[i + 1] - b;
                }
            }
        }
    }
    for (int i = 1; i <= n; ++ i)
    {
        answer(i, res[i]);
    }
}
/*void read()
{

}
void solve()
{

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}*/

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