Submission #704262

#	Time	Username	Problem	Language	Result	Execution time	Memory
704262		CDuong	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	208 KiB

xylophone

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#include "xylophone.h"
#define taskname ""
#define all(x) x.begin(), x.end()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
using namespace std;

const int mxN = 5e3 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;

void solve(int N) {
    int n = N;
    int diff_1[n + 5], diff_2[n + 5];
    for(int i = 1; i <= n - 1; ++i)
        diff_1[i] = query(i, i + 1);
    for(int i = 1; i <= n - 2; ++i)
        diff_2[i] = query(i, i + 2);
    int diff[n + 5]; diff[1] = 0;
    bool last_time = true;
    for(int i = 1; i <= n - 2; ++i) {
        if(diff_1[i] + diff_1[i + 1] == diff_2[i]) {
            if(last_time) {
                diff[i + 1] = diff[i] + diff_1[i];
                diff[i + 2] = diff[i] + diff_2[i];
            }
            else {
                diff[i + 1] = diff[i] - diff_1[i];
                diff[i + 2] = diff[i] - diff_2[i];
            }
        }
        else {
            if(last_time) {
                diff[i + 1] = diff[i] + diff_1[i];
                diff[i + 2] = diff[i] + diff_1[i] - diff_1[i + 1];
            }
            else {
                diff[i + 1] = diff[i] - diff_1[i];
                diff[i + 2] = diff[i] - diff_1[i] + diff_1[i + 1];
            }
            last_time ^= 1;
        }
    }

    int pos_max = 1, pos_min = 1, cur_max = 0, cur_min = 0;
    for(int i = 2; i <= n; ++i) {
        cur_max = max(cur_max, diff[i]);
        cur_min = min(cur_min, diff[i]);
        pos_max = (cur_max == diff[i] ? i : pos_max);
        pos_min = (cur_min == diff[i] ? i : pos_min);
    }

    // for(int i = 1; i <= n; ++i)
    //     cout << i << " " << diff[i] << endl;
    // cout << endl;

    int coef = 1;
    if(pos_max < pos_min)
        coef = -1;

    int first_element = 1 - diff[min(pos_min, pos_max)] * coef;
    answer(1, first_element);
    for(int i = 2; i <= n; ++i)
        answer(i, first_element + diff[i] * coef);
}

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