제출 #61357

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61357		the_art_of_war	Xylophone (JOI18_xylophone)	C++14	0 / 100	4 ms	640 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
static int A[5000];
using namespace std;

int get(int x1,int x2,int x3){
    return max(x1,max(x2,x3)) - min(x1,min(x2,x3));
}

void solve(int N) {

     int n = N;
	 int pos = -1; // pos of 1
	 int l = 1, r = n-1;
	 while(l<=r){
        int mid = (l+r)>>1;
        if(query(mid,N) == n-1){
            pos = mid;
            r = mid-1;
        } else{
            l = mid+1;
        }
	 }
	 assert(pos>=1);
	 A[pos] = 1;
	 set<int> vals;
	 vals.insert(1);
     for(int i=pos-1;i>=1;--i){
        int x = query(i,i+1);
        int val1 = A[i+1] + x;
        int val2 = A[i+1] - x;
        bool good1 = val1 >=1 && val1<=n && !vals.count(val1);
        bool good2 = val2>=1  && val2<=n && !vals.count(val2);
        if(good1 && good2){
            int x = query(i,i+2);
            good1 = get(val1,A[i+1],A[i+2]) == x;
            good2 = get(val2,A[i+1],A[i+2]) == x;
            if(good1 && good2)
                assert(false);
            if(good1){
                A[i] = val1;
            } else if(good2){
                A[i] = val2;
            }
        } else{
            if(good1){
                A[i] = val1;
            } else if(good2){
                A[i] = val2;
            } else {
                assert(false);
            }
        }
        vals.insert(A[i]);
     }

     for(int i=pos+1;i<=n;++i){
        int x = query(i-1,i);
        int val1 = A[i-1] + x;
        int val2 = A[i-1] - x;
        bool good1 = val1 >=1 && val1<=n && !vals.count(val1);
        bool good2 = val2>=1  && val2<=n && !vals.count(val2);
        if(good1 && good2){
            int x = query(i-2,i);
            good1 = get(val1,A[i-1],A[i-2]) == x;
            good2 = get(val2,A[i-1],A[i-2]) == x;
            if(good1 && good2)
                assert(false);
            if(good1){
                A[i] = val1;
            } else if(good2){
                A[i] = val2;
            }
        } else{
            if(good1){
                A[i] = val1;
            } else if(good2){
                A[i] = val2;
            } else {
                assert(false);
            }
        }
        vals.insert(A[i]);
     }


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



}

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