Submission #253529

#	Time	Username	Problem	Language	Result	Execution time	Memory
253529		aggu_01000101	Xylophone (JOI18_xylophone)	C++14	100 / 100	66 ms	892 KiB

xylophone

#include <iostream>
#include <xylophone.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <iomanip>
#include <bits/stdc++.h>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
//#define int long long
#define INF -1
#define mid(l, u) ((l+u)/2)
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
using namespace std;
initrand;
int N;
map<int, bool> seen;
/*int query(int s, int t){
    cout<<"Query asked: "<<s<<" "<<t<<endl;
    int ans;
    cin>>ans;
    return ans;
}
void answer(int i, int a){
    cout<<"Answer for index "<<i<<" is "<<a<<endl;
}*/
int findOne(int n){
    int l = 2;
    int u = n;
    int tr = n-1;
    while(l<=u){
        int m = mid(l, u);
        if(query(m, n) < (n-1)){
            tr = min(tr, m-1);
            u = m-1;
        }
        else l = m+1;
    }
    return tr;
}
int diff(int a, int b, int c){
    return max(a, max(b, c)) - min(a, min(b, c));
}
int findPrev(int i, int prev, int prev1){
    int temp = query(i, i+1);
    int poss1 = prev+temp;
    int poss2 = prev-temp;
    if(seen[poss1] || poss1>N) return poss2;
    if(seen[poss2] || poss2<1) return poss1;
    temp = query(i, i+2);
    if(temp == diff(prev, prev1, poss1)) return poss1;
    return poss2;
}
int findNext(int i, int prev, int prev1){
    int temp = query(i-1, i);
    int poss1 = prev+temp;
    int poss2 = prev-temp;
    if(seen[poss1] || poss1>N) return poss2;
    if(seen[poss2] || poss2<1) return poss1;
    temp = query(i-2, i);
    if(temp == diff(prev, prev1, poss1)) return poss1;
    return poss2;
}
void solve(int n){
    N = n;
    int arr[n+1];
    int oind = findOne(n);
    arr[oind] = 1;
    seen[1] = true;
    arr[oind + 1] = 0;
    for(int j = oind-1;j>=1;j--){
        arr[j] = findPrev(j, arr[j+1], arr[j+2]);
        seen[arr[j]] = true;
    }
    for(int j = oind+1;j<=n;j++){
        arr[j] = findNext(j, arr[j-1], ((j-2)>=1)?arr[j-2]:0);
        seen[arr[j]] = true;
    }
    for(int i = 1;i<=n;i++) answer(i, arr[i]);
}

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