Submission #333819

#	Time	Username	Problem	Language	Result	Execution time	Memory
333819		Swan	Xylophone (JOI18_xylophone)	C++14	0 / 100	0 ms	364 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
#define stop system("pause")
#define INP freopen("snowcow.in","r",stdin)
#define OUTP freopen("snowcow.out","w",stdout)

using namespace std;


void check(vector<int>& signSwap, vector<int>& diff, int sign){
    int now = sign * diff[0];
    int one = 0;
    int mn = min(0, now);
    if(now < 0){
        one = 1;
    }
    for(int i = 0; i < (int)signSwap.size();i++){
        if(signSwap[i])sign = -sign;
        now+=sign * diff[i + 1];
        if(now < mn){
            mn = now;
            one = i + 2;
        }
    }
    vector<int> ans;
    int ansSize = diff.size() + 1;
    ans.resize(ansSize);
    ans[one] = 1;
    sign = -1;
    for(int i = one + 1;i < ansSize; i++){
        if(signSwap[i - 2])sign = -sign;
        ans[i] = ans[i - 1] + diff[i - 1] * sign;
        if(ans[i] > ansSize || ans[i] <= 0){
            return;
        }
    }
    sign = -1;
    for(int i = one - 1;i >= 0; i--){
        if(signSwap[i])sign = -sign;
        ans[i] = ans[i + 1] + diff[i] * sign;
        if(ans[i] > ansSize || ans[i] <= 0 || ans[i] == ansSize){
            return;
        }
    }
    for(int i = 0 ; i < (int)ans.size();i++){
        answer(i + 1, ans[i]);
    }
}

void solve(int n){
    vector<int> two;
    vector<int> three;
    if(n == 2){
        answer(1, 1);
        answer(2, 2);
        return;
    }
    for(int l = 1; l <=n;l++){
        two.push_back(query(l, l + 1));
        if(l + 2 <= n)three.push_back(query(l, l + 2));
    }
    vector<int> signSwap;
    for(int i = 0; i < (int)two.size() - 1;i++){
        if(two[i] + two[i + 1] == three[i]){
            signSwap.push_back(0);
        }else{
            signSwap.push_back(1);
        }
    }
    check(signSwap, two, -1);
    check(signSwap, two, 1);
}

/*
7
2 3 4 1 5 7 6
5
1 4 2 3 5
8
6 2 3 1 8 5 4 7
3
1 2 3
3
2 1 3
9
5 7 8 2 3 1 9 6 4
*/

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