# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1277094 | nanaseyuzuki | Xylophone (JOI18_xylophone) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "xylophone.h"
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;
const int mn = 1e6 + 1, bm = (1 << 15) + 1, mod = 1532023;
const int inf = 1e9, base = 311;
vector <int> merge(int ll, int rr){
if(ll == rr){
vector <int> ans;
ans.push_back(ll);
return ans;
}
vector <int> ans;
int mid = (ll + rr) >> 1;
vector <int> l = merge(ll, mid);
vector <int> r = merge(mid + 1, rr);
int i = 0, j = 0;
while(i < l.size() && j < r.size()){
int kq = query(l[i], r[j]);
if(kq < 0){
ans.push_back(l[i]);
i ++;
}
else{
ans.push_back(r[j]);
j ++;
}
}
while(i < l.size()) ans.push_back(l[i++]);
while(j < r.size()) ans.push_back(r[j++]);
return ans;
}
void solve(int N) {
int n = N;
vector <int> kq = merge(1, n);
vector <pii> Megumi;
for(int i = 0; i < n; i++){
Megumi.push_back({kq[i], i + 1});
}
sort(all(Megumi));
for(auto [j, i] : Megumi) answer(j, i + 1);
}