oj.uz

Submission #61357

# Submission time Handle Problem Language Result Execution time Memory
61357 2018-07-25T16:15:04 Z the_art_of_war Xylophone (JOI18_xylophone) C++14
0 / 100
 4 ms 640 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Runtime error 4 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Runtime error 4 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Runtime error 4 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -