제출 #342211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
342211		bigDuck	Xylophone (JOI18_xylophone)	C++14	100 / 100	143 ms	1288 KiB

xylophone

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount


#include "xylophone.h"

/*
    query(s, t);
    answer(i, a);
*/

int d[5010][2];

map<int, int> h;

int a[5010];

int sgn[5010];

void solve(int N) {
    int n=N;

    for(int i=2; i<=n; i++){
        d[i][0]=query(i-1, i);
        if(i>2){
            d[i][1]=query(i-2, i);
        }
    }

    //d[2][0]=|a2-a1|

    //pozitiv
    int f=0, l=0;
    bool ok=true;
    sgn[2]=+1;
    int sum=d[2][0];
    h[0]=1;
    h[sum]=2;
    if(h[sum-(n-1)]!=0){
        f=h[sum-(n-1)], l=2;
    }
    for(int i=3; i<=n; i++){
        int d1=d[i-1][0], d2=d[i][0], d3=d[i][1];
        if(d3==(d1+d2)){
            sgn[i]=sgn[i-1];
        }
        else{
            sgn[i]=-sgn[i-1];
        }
        sum+=sgn[i]*d[i][0];
        h[sum]=i;
        if(h[sum+(n-1)]!=0 ){
            ok=false; break;
        }
        if(h[sum-(n-1) ]!=0){
            f=h[sum-(n-1)]; l=i;
        }
    }

    if(ok){


        a[f]=1; a[l]=N;

            a[f]=1; a[l]=N;

    for(int i=f-1; i>=1; i--){
        a[i]=a[i+1]-sgn[i+1]*d[i+1][0];
    }
    for(int i=f+1; i<=N; i++){
        a[i]=a[i-1]+sgn[i]*d[i][0];
    }

    for(int i=1; i<=n; i++){
            //cout<<a[i]<<endl;
        answer(i, a[i]);
    }

    return;
    }


    h.clear();
    sgn[2]=-1;
    sum=-d[2][0];
    h[0]=1;
    h[sum]=2;
    if(h[sum-(n-1)]!=0){
        f=h[sum-(n-1)], l=2;
    }
    for(int i=3; i<=n; i++){
        int d1=d[i-1][0], d2=d[i][0], d3=d[i][1];
        if(d3==(d1+d2)){
            sgn[i]=sgn[i-1];
        }
        else{
            if( (d3==(d1)) || (d3==(d2)) ){
                sgn[i]=-sgn[i-1];
            }
        }
        sum+=sgn[i]*d[i][0];
        h[sum]=i;
        if(h[sum-(n-1)]!=0 ){
            f=h[sum-(n-1)], l=i;
        }
    }
    a[f]=1; a[l]=N;

    for(int i=f-1; i>=1; i--){
        a[i]=a[i+1]-sgn[i+1]*d[i+1][0];
    }
    for(int i=f+1; i<=N; i++){
        a[i]=a[i-1]+sgn[i]*d[i][0];
    }
    for(int i=1; i<=n; i++){
        answer(i, a[i]);
    }

}

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