| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 433716 | HediChehaidar | Xylophone (JOI18_xylophone) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
ID: hedichehaidar
TASK: photo
LANG: C++11
*/
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vdd vector<pdd>
#define dte tuple<double , double , double>
using namespace std;
const int INF = 1000*1000*1000; // 1 e 9
const int MOD = INF + 7;
const double EPS = 0.000000001; // 1 e -9
const ll inf = (ll)1e18;
int n;
vi v;
/*int query(int i , int j){
// cout << i << " " << j << endl;
int mn = INF, mx = -1;
for(int x = i - 1 ; x <= j - 1 ; x++){
mn = min(mn , v[x]);
mx = max(mx , v[x]);
}
return mx - mn;
}
int answer(int i , int a){
cout << i << " " << a << "\n";
}*/
bool seen[5050];
vi res;
void solve(int N){
n = N;
res.assign(n , 0);
int l = 0 , r = n - 1;
int ans = -1 , d = n - 1;
while(l <= r){
int mid = (l + r) / 2 ;
int q = query(1 , mid);
if(q != d){
l = mid + 1;
}
else{
ans = mid;
r = mid - 1;
}
}
l = 0 ; r = ans;
int ans2 = -1;
while(l <= r){
int mid = (l+ r) / 2;
int q = query(mid , ans);
if(q != d){
r = mid - 1;
}
else{
ans2 = mid;
l = mid + 1;
}
}
swap(ans , ans2);
res[ans - 1] = 1;
res[ans2 - 1] = n;
if(ans != 1) {
res[ans - 2] = query(ans - 1 , ans) + 1;
}
if(ans2 != n){
res[ans2] = res[ans2 - 1] - query(ans2 , ans2 + 1);
}
if(ans != ans2 - 1){
res[ans] = query(ans , ans + 1) + 1;
if(ans != ans2 - 2){
res[ans2 - 2] = res[ans2 - 1] - query(ans2 - 1 , ans2);
}
}
for(auto c : res ) seen[c] = true;
int cur = ans - 2;
while(cur >= 0){
int q1 = query(cur + 1 , cur + 2);
if(res[cur + 1] - q1 < 1 || seen[res[cur + 1] - q1]){
res[cur] = res[cur + 1] + q1;
}
else if(res[cur + 1] + q1 > n || seen[res[cur + 1] + q1]){
res[cur] = res[cur + 1] - q1;
}
else{
int q2 = query(cur + 1 , cur + 3);
if(q1 == q2){
if(res[cur + 1] < res[cur + 2]){
res[cur] = res[cur + 1] + q1;
}
else res[cur] = res[cur + 1] - q1;
}
else if(q2 == abs(res[cur + 1] - res[cur + 2])){
if(res[cur + 1] < res[cur + 2]) res[cur] = res[cur + 1] + q1;
else res[cur] = res[cur + 1] - q1;
}
else if(res[cur + 1] > res[cur + 2]) res[cur] = res[cur + 1] + q1;
else res[cur] = res[cur + 1] - q1;
}
seen[res[cur]] = true;
cur--;
}
/* for(int i = 0 ; i < ans ; i ++) {
if(v[i] != res[i]) {
cout << "wrong\n"; return;
}
}*/
cur = ans2 + 1 ;
while(cur < n){
int q1 = query(cur , cur + 1);
// cout << q1 << endl;
if(res[cur - 1] - q1 < 1 || seen[res[cur - 1] - q1]){
res[cur] = res[cur - 1] + q1;
// if(res[cur] > 5049) cout << "here" << endl;
}
else if(res[cur - 1] + q1 > n || seen[res[cur - 1] + q1]){
res[cur] = res[cur - 1] - q1;
}
else{
int q2 = query(cur - 1 , cur + 1);
//cout << cur << " " << q2 << endl;
if(q1 == q2){
if(res[cur - 1] < res[cur - 2]){
res[cur] = res[cur - 1] + q1;
}
else res[cur] = res[cur - 1] - q1;
}
else if(q2 == abs(res[cur - 1] - res[cur - 2])){
if(res[cur - 1] < res[cur - 2]) res[cur] = res[cur - 1] + q1;
else res[cur] = res[cur - 1] - q1;
}
else if(res[cur - 1] > res[cur - 2]) res[cur] = res[cur - 1] + q1;
else res[cur] = res[cur - 1] - q1;
}
// cout << res[cur] << endl;
seen[res[cur]] = true;
if(res[cur] != v[cur]){
cout << cur << " " << res[cur] << " " << v[cur] <<"\n";
return;
}
cur++;
}
for(int i = 0 ; i < n ; i++) answer(i + 1 , res[i]);
/* for(int i = ans ; i < n ; i++){
if(res[i] != v[i]) cout << "wrong2\n"; return;
}*/
//cout << "here" << endl;
}
/*int main(){
//ifstream fin ("race.in");
//ofstream fout ("race.out");
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int N = 5*1000;
for(int i = 0 ; i < N ; i++){
int x = i + 1;
v.pb(x);
}
random_shuffle(all(v));
int N; cin>>N;
for(int i = 0 ; i < N ; i++) {
int x; cin>>x;
v.pb(x);
}
solve(N);
// for(auto c : res) cout << c << " " ; cout << "\n";
for(int i = 0 ; i < n ; i++){
if(res[i] != v[i]) return cout << "wrong\n",0;
}
cout << "ok\n";
return 0;
}*/
/*
Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO
Read the statement CAREFULLY !!
Make a GREADY APPROACH !!!! (start from highest / lowest)
Make your own TESTS !!
Be careful from CORNER CASES !
*/