oj.uz

Submission #299794

# Submission time Handle Problem Language Result Execution time Memory
299794 2020-09-15T16:33:38 Z limabeans Xylophone (JOI18_xylophone) C++17
11 / 100
 87 ms 504 KB 
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

void solve(int N);
int query(int s, int t);
void answer(int i, int a);


using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;

int A[maxn];

void Set(int i, int a) {
    answer(i,a);
    A[i]=a;
}

void solve(int l, int r, bool big, int idx) {
    if (r-l<=0) return;
    int gap = query(l,r);
    if (idx==l) {
	int lo = l;
	int hi = r;
	while (hi-lo>1) {
	    int m=(lo+hi)/2;
	    if (query(l,m)==gap) {
		hi = m;
	    } else {
		lo = m;
	    }
	}
	int mid = hi;
	// L....mid....r
	if (big) {
	    Set(mid,A[idx]-gap);
	    solve(l,mid-1,true,l);  // [l,mid)
	    solve(mid,r,false,mid); // [mid,r]
	} else {
	    Set(mid,A[idx]+gap);
	    solve(l,mid-1,false,l); // [l,mid)
	    solve(mid,r,true,mid);  // [mid,r]
	}
	
    } else if (idx==r) {
	int lo = l;
	int hi = r;
	while (hi-lo>1) {
	    int m=(lo+hi)/2;
	    if (query(m,r)==gap) {
		lo = m;
	    } else {
		hi = m;
	    }
	}
	int mid = lo;
	// l....mid....R
	if (big) {
	    Set(mid,A[idx]-gap);
	    solve(l,mid,false,mid);  // [l,mid]
	    solve(mid+1,r,true,r);   // (mid,r]
	} else {
	    Set(mid,A[idx]+gap);
	    solve(l,mid,true,mid);   // [l,mid]
	    solve(mid+1,r,false,r);  // (mid,r]
	}
    } else {
	assert(false);
    }
}




void solve(int n) {
    // find 1 and n
    int i1 = -1;
    int in = -1;
    for (int i=1; in==-1 && i<=n; i++) {
	for (int j=i; in==-1 && j<=n; j++) {
	    if (query(i,j)==n-1) {
		in=j;
		break;
	    }
	}
    }
    assert(~in);

    for (int j=in; i1==-1 && j>=1; j--) {
	if (query(j,in)==n-1) {
	    i1=j;
	    break;
	}
    }
    assert(~i1);

    Set(i1,1);
    Set(in,n);

    solve(1,i1,false,i1);
    solve(i1,in-1,false,i1);
    solve(in,n,true,in);
    // 1...i1.....in...n
}

///////////////////////////////////////////////////////////////////////////

/*
int nn;
vector<int> v = {-1,4,6,5,1,7,3,2,9,8};
int query(int s, int t) {
    assert(s<=t);
    int mx=0;
    for (int i=s; i<=t; i++) {
	for (int j=i; j<=t; j++) {
	    mx=max(mx,abs(v[i]-v[j]));
	}
    }
    return mx;
}


void answer(int i, int a) {
    A[i]=a;
}

void print() {
    cout<<"v: ";
    for (int i=1; i<=nn; i++) {
	cout<<v[i]<<" ";
    }
    cout<<endl;
    cout<<"A: ";
    for (int i=1; i<=nn; i++) {
	cout<<A[i]<<" ";
    }
    cout<<endl;
}

vector<int> rand_perm(int n, int index=1) {
    assert(n>=1);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<int> a(n);
    iota(a.begin(), a.end(), index);
    shuffle(a.begin(), a.end(), rng);
    return a;
}

vector<int> genV(int n) {
    vector<int> v = rand_perm(n, 1);
    v.insert(v.begin(), -1);
    int i1= -1; int in = -1;
    for (int i=1; i<=n; i++) {
	if (v[i]==1) i1=i;
	if (v[i]==n) in=i;
    }
    if (i1>in) {
	swap(v[i1],v[in]);
    }
    return v;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    v = genV(10);
    nn = (int)v.size() - 1;
    solve(nn);
    print();
    for (int i=1; i<=nn; i++) {
	assert(A[i]==v[i]);
    }
    
    
    return 0;
}

*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 416 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 7 ms 256 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 3 ms 256 KB Output is correct
13 Correct 3 ms 256 KB Output is correct
14 Correct 3 ms 256 KB Output is correct
15 Correct 4 ms 256 KB Output is correct

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 416 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 7 ms 256 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 3 ms 256 KB Output is correct
13 Correct 3 ms 256 KB Output is correct
14 Correct 3 ms 256 KB Output is correct
15 Correct 4 ms 256 KB Output is correct
16 Correct 8 ms 256 KB Output is correct
17 Correct 17 ms 256 KB Output is correct
18 Correct 32 ms 384 KB Output is correct
19 Correct 38 ms 256 KB Output is correct
20 Correct 41 ms 384 KB Output is correct
21 Correct 26 ms 256 KB Output is correct
22 Correct 21 ms 376 KB Output is correct
23 Incorrect 87 ms 504 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 416 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 7 ms 256 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 3 ms 256 KB Output is correct
13 Correct 3 ms 256 KB Output is correct
14 Correct 3 ms 256 KB Output is correct
15 Correct 4 ms 256 KB Output is correct
16 Correct 8 ms 256 KB Output is correct
17 Correct 17 ms 256 KB Output is correct
18 Correct 32 ms 384 KB Output is correct
19 Correct 38 ms 256 KB Output is correct
20 Correct 41 ms 384 KB Output is correct
21 Correct 26 ms 256 KB Output is correct
22 Correct 21 ms 376 KB Output is correct
23 Incorrect 87 ms 504 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -