Submission #23184

#	Time	Username	Problem	Language	Result	Execution time	Memory
23184		duongthoi1999	Park (JOI17_park)	C++14	10 / 100	56 ms	2116 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef long double ld;
typedef pair<ll, int> ii;
const int mod = (int) 1e9 + 7;
const ll inf = 1LL << 60;
const int maxn = (int) 3e5 + 5;
const ld eps = 1e-9;

int n, Place[1400];

void subtask1() {
    rep(i, 0, n) Place[i] = 0;
	rep(i, 0, n) {
        rep(j, i + 1, n) {
            Place[i] = Place[j] = 1;
            if(Ask(i, j, Place)) Answer(i, j);
            Place[i] = Place[j] = 0;
        }
    }
}

void do_sort(int l, int r, vector<int> &a) {
    if(l + 2 >= r) return ;
    //cerr << "? " << l << ' ' << r << endl;
    int x = a[l + 1 + rand() % (r - l - 1)];
    //cerr << "! " << x << endl;
    //cerr << "Before: ";
    //rep(i, 0, n) cerr << a[i] << ' ';
    //cerr << endl;

    vector<int> L, R;
    rep(i, l + 1, r) if(a[i] != x) {
        Place[a[i]] = 0;
        if(Ask(l, x, Place)) R.pb(a[i]);
        else L.pb(a[i]);
        Place[a[i]] = 1;
    }
    rep(i, 0, SZ(L)) a[l + 1 + i] = L[i];
    int md = l + 1 + SZ(L);
    a[md] = x;
    rep(i, 0, SZ(R)) a[md + 1 + i] = R[i];
    //cerr << "After: ";
    //rep(i, 0, n) cerr << a[i] << ' ';
    //cerr << endl;
    do_sort(l, md, a);
    do_sort(md, r, a);
}

void subtask2() {
    srand(time(NULL));
    vector<int> a(n, -1);
    rep(i, 0, n) a[i] = i, Place[i] = 1;
    do_sort(0, n - 1, a);
    rep(i, 0, n - 1) Answer(min(a[i], a[i + 1]), max(a[i], a[i + 1]));
}

void subtask3() {

}

void subtask4() {

}

void subtask5() {

}
void Detect(int T, int N) {
	n = N;
	if(T == 1) subtask1();
	if(T == 2) subtask2();
	if(T == 3) subtask3();
	if(T == 4) subtask4();
	if(T == 5) subtask5();
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30
• Subtask 5: 0 / 23