Submission #70950

#	Time	Username	Problem	Language	Result	Execution time	Memory
70950		dmfr	Xylophone (JOI18_xylophone)	C++11	0 / 100	4 ms	308 KiB

xylophone

#include "xylophone.h"
#include <vector>

#include <iostream>

using namespace std;

/*
5
2 1 5 3 4
*/

void solve(int N) {
    int K = query(1,N);

    int minIndex;{
        int m, k;
        int left, right;
        left = 1;
        right = N-1;
        while(left != right){
            m = (left+right)/2+1;
            k = query(m, N);
            if(k == K) left  = m;
            else       right = m-1;
        }
        minIndex = left;
    }

    vector<bool> UsedNumbers(N+1, false);

    vector<int> kVtr(N+1);
    for(int i = 2; i <= N; ++i)
        kVtr[i] = query(i-1,i);

    vector<int> Solution(N+1);

    Solution[minIndex] = 1;
    UsedNumbers[Solution[minIndex]] = true;
        Solution[minIndex+1] = Solution[minIndex] + kVtr[minIndex+1];
        UsedNumbers[Solution[minIndex+1]] = true;
    if(minIndex != 1){
        Solution[minIndex-1] = Solution[minIndex] + kVtr[minIndex];
        UsedNumbers[Solution[minIndex+1]] = true;
    }

    int k, kM, km, k_;
    ///After minIndex
    for(int i = minIndex+2; i <= N; ++i){
        k = kVtr[i];
        kM = Solution[i-1] + k;
        km = Solution[i-1] - k;
        if((km < 1) || (UsedNumbers[km])){Solution[i] = kM; continue;}
        if((kM > N) || (UsedNumbers[kM])){Solution[i] = km; continue;}

        k_ = query(i-2,i);

        Solution[i] = Solution[i-1];
        if(Solution[i-2] < Solution[i-1]){                     ///^
            if(kVtr[i-1]+kVtr[i] == k_) Solution[i] += kVtr[i];  ///^^
            else                        Solution[i] -= kVtr[i];  ///^v
        }else{                                                 ///v
            if(kVtr[i-1]+kVtr[i] == k_) Solution[i] -= kVtr[i];  ///vv
            else                        Solution[i] += kVtr[i];  ///v^
        }
    }
    ///Before minIndex
    for(int i = minIndex-2; i >= 1; --i){
        k = kVtr[i+1];
        kM = Solution[i+1] + k;
        km = Solution[i+1] - k;
        if((km < 1) || (UsedNumbers[km])){Solution[i] = kM; continue;}
        if((kM > N) || (UsedNumbers[kM])){Solution[i] = km; continue;}

        k_ = query(i,i+2);

        Solution[i] = Solution[i+1];
        if(Solution[i+1] < Solution[i+2]){                     ///v
            if(kVtr[i-1]+kVtr[i] == k_) Solution[i] -= kVtr[i];  ///vv
            else                        Solution[i] += kVtr[i];  ///v^
        }else{                                                 ///^
            if(kVtr[i-1]+kVtr[i] == k_) Solution[i] += kVtr[i];  ///^^
            else                        Solution[i] -= kVtr[i];  ///^v
        }
    }




//    cout << "minindex=" << minIndex << " maxindex=" << maxIndex << endl;


//    cout << "Solution:" << endl;
//    for(int i = 1; i <= N; ++i)
//        cout << Solution[i] << endl;
//    cout << endl;






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

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