oj.uz

Submission #23186

# Submission time Handle Problem Language Result Execution time Memory
23186 2017-05-04T11:14:59 Z duongthoi1999 Park (JOI17_park) C++14
20 / 100
 203 ms 2116 KB 
#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;

bool ask(int A, int B, int Place[]) {
    if(A > B) swap(A, B);
    return Ask(A, B, Place);
}

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(a[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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2116 KB Output is correct
2 Correct 6 ms 2116 KB Output is correct
3 Correct 6 ms 2116 KB Output is correct
4 Correct 6 ms 2116 KB Output is correct
5 Correct 6 ms 2116 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 2116 KB Output is correct
2 Correct 119 ms 2116 KB Output is correct
3 Correct 113 ms 2116 KB Output is correct
4 Correct 199 ms 2116 KB Output is correct
5 Correct 203 ms 2116 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2116 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2116 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2116 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -