oj.uz

Submission #299793

# Submission time Handle Problem Language Result Execution time Memory
299793 2020-09-15T16:21:44 Z limabeans Xylophone (JOI18_xylophone) C++17
11 / 100
 93 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;
    if (idx==l) {
	int gap=0;
	int mid=-1;
	for (int i=l+1; i<=r; i++) {
	    int res = query(l,i);
	    if (res>gap) {
		gap=res;
		mid=i;
	    }
	}
	assert(~mid);
	// 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 gap=0;
	int mid=-1;
	for (int i=r-1; i>=l; i--) {
	    int res=query(i,r);
	    if (res>gap) {
		gap=res;
		mid=i;
	    }
	}
	assert(~mid);
	// 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 0 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 43 ms 376 KB Output is correct
6 Correct 7 ms 256 KB Output is correct
7 Correct 6 ms 256 KB Output is correct
8 Correct 8 ms 256 KB Output is correct
9 Correct 35 ms 504 KB Output is correct
10 Correct 42 ms 256 KB Output is correct
11 Correct 7 ms 256 KB Output is correct
12 Correct 4 ms 256 KB Output is correct
13 Correct 6 ms 256 KB Output is correct
14 Correct 8 ms 256 KB Output is correct
15 Correct 7 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 0 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 43 ms 376 KB Output is correct
6 Correct 7 ms 256 KB Output is correct
7 Correct 6 ms 256 KB Output is correct
8 Correct 8 ms 256 KB Output is correct
9 Correct 35 ms 504 KB Output is correct
10 Correct 42 ms 256 KB Output is correct
11 Correct 7 ms 256 KB Output is correct
12 Correct 4 ms 256 KB Output is correct
13 Correct 6 ms 256 KB Output is correct
14 Correct 8 ms 256 KB Output is correct
15 Correct 7 ms 256 KB Output is correct
16 Correct 17 ms 408 KB Output is correct
17 Correct 52 ms 384 KB Output is correct
18 Correct 93 ms 384 KB Output is correct
19 Incorrect 83 ms 256 KB Wrong Answer [2]
20 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 0 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 43 ms 376 KB Output is correct
6 Correct 7 ms 256 KB Output is correct
7 Correct 6 ms 256 KB Output is correct
8 Correct 8 ms 256 KB Output is correct
9 Correct 35 ms 504 KB Output is correct
10 Correct 42 ms 256 KB Output is correct
11 Correct 7 ms 256 KB Output is correct
12 Correct 4 ms 256 KB Output is correct
13 Correct 6 ms 256 KB Output is correct
14 Correct 8 ms 256 KB Output is correct
15 Correct 7 ms 256 KB Output is correct
16 Correct 17 ms 408 KB Output is correct
17 Correct 52 ms 384 KB Output is correct
18 Correct 93 ms 384 KB Output is correct
19 Incorrect 83 ms 256 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -