Submission #469814

#	Time	Username	Problem	Language	Result	Execution time	Memory
469814		ljuba	Xylophone (JOI18_xylophone)	C++17	100 / 100	134 ms	432 KiB

xylophone

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

using namespace std;

void solve(int N) {
    vector<int> v(N+1), v2(N+1);

    for(int i = 1; i + 1 <= N; ++i) {
        v[i] = query(i, i+1);
    }

    for(int i = 1; i + 2 <= N; ++i) {
        v2[i] = query(i, i+2);
    }

    vector<int> znak(N+1, 1);
    vector<int> konacno(N+1);
    konacno[2] = v[1];

    //znak[2] je 1

    for(int i = 3; i <= N; ++i) {
        znak[i] = znak[i-1];
        if(v[i-2] + v[i-1] != v2[i-2]) {
            znak[i] = znak[i-1] * (-1);
        }
        konacno[i] = konacno[i-1] + znak[i] * v[i-1];
    }

    int mini = 1, maksi = 1;

    for(int i = 2; i <= N; ++i) {
        if(konacno[i] < konacno[mini]) {
            mini = i;
        }
        if(konacno[i] > konacno[maksi]) {
            maksi = i;
        }
    }

    if(mini > maksi) {
        for(int i = 2; i <= N; ++i) {
            znak[i] *= (-1);
            konacno[i] = konacno[i-1] + znak[i] * v[i-1];
        }

        mini = 1;
        for(int i = 2; i <= N; ++i) {
            if(konacno[i] < konacno[mini]) {
                mini = i;
            }
        }
    }

    vector<int> ans(N+1);

    for(int i = 1; i <= N; ++i) {
        ans[i] = (konacno[i] - konacno[mini] + 1);
    }

    for(int i = 1; i <= N; ++i) {
        answer(i, ans[i]);
    }
}

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