Submission #61375

#	Time	Username	Problem	Language	Result	Execution time	Memory
61375		the_art_of_war	Xylophone (JOI18_xylophone)	C++14	100 / 100	111 ms	956 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;
       //     cout <<"hre "<<mid<<endl;
            l = mid+1;
        } else{
            r = mid-1;
        }
	 }
	 assert(pos>=1);
//	 cerr <<"POs : "<<pos<<endl;
	 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);
     //   cerr << i <<"  : " <<val1<<" "<< val2<<endl;
        if(good1 && good2){
            int x = query(i,i+2);
    //        cerr <<" here "<<x<<endl;
            good1 = get(val1,A[i+1],A[i+2]) == x;
            good2 = get(val2,A[i+1],A[i+2]) == x;
  //          cerr << " "<<good1 <<" "<<good2<<endl;
            if(good1 && good2){
         //       assert(false);
            }
            if(good1){
                A[i] = val1;
    //            cerr <<"A[1] " <<A[i]<<endl;
            } 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);
    //    cerr << i << " : " << val1<<" "<<val2<<endl;
        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){
        cerr << A[i]<<" ";
     }
     cerr << endl;*/


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



}

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