Submission #61360

#	Time	Username	Problem	Language	Result	Execution time	Memory
61360		the_art_of_war	Xylophone (JOI18_xylophone)	C++14	0 / 100	5 ms	644 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
static int A[5100];
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]);
     }



}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:38:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
             if(good1 && good2)
               ^
xylophone.cpp:67:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
             if(good1 && good2)
               ^

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