oj.uz

Submission #29019

# Submission time Handle Problem Language Result Execution time Memory
29019 2017-07-18T06:23:53 Z 상수시러(#1235) Park (JOI17_park) C++11
47 / 100
 283 ms 2384 KB 
#include "park.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> PL;
typedef long double ldouble;

static int place[1400];
int N;
int reorder[1400];

void myAnswer_2(int x, int y) {
    if(x > y) swap(x, y);
    Answer(x, y);
}

void Do_2(vector <int> &V) {
    int x = V[0];
    vector <int> w[2];
    for(int i=1;i<sz(V);i++) {
        rep(k, N) place[k] = 1;
        place[V[i]] = 0;
        int t = Ask(0, x, place);
        w[t].pb(V[i]);
    }
    if(sz(w[0])) {
        Do_2(w[0]);
        myAnswer_2(w[0].back(), x);
    }
    if(sz(w[1])) {
        Do_2(w[1]);
        myAnswer_2(x, w[1][0]);
    }
    V.clear();
    for(int e : w[0]) V.pb(e);
    V.pb(x);
    for(int e : w[1]) V.pb(e);
}

void myAnswer_3(int x, int y) {
    x = reorder[x], y = reorder[y];
    if(x > y) swap(x, y);
    Answer(x, y);
}

int myAsk_3(int x, int y, vector <int> v) {
    rep(i, N) place[i] = 0;
    for(int e : v) place[reorder[e]] = 1;
    x = reorder[x], y = reorder[y];
    if(x > y) swap(x, y);
    return Ask(x, y, place);
}

void dfs(int x, vector <int> &V) {
    random_shuffle(all(V));
    vector <int> child;
    for(int e : V) {
        vector <int> temp; temp.pb(x); temp.pb(e);
        if(myAsk_3(x, e, temp)) {
            myAnswer_3(x, e);
            child.pb(e);
        }
    }
    vector <vector <int> > L;
    L.resize(sz(child));
    random_shuffle(all(child));
    set <int> temp;
    for(int e : child) temp.insert(e);
    for(int i=0;i<sz(child);i++) {
        for(int e : V) {
            if(temp.find(e) == temp.end()) {
                vector <int> tv;
                for(int i=0;i<N;i++) if(i != x) tv.pb(i);
                int t = myAsk_3(child[i], e, tv);
                if(t == 1) {
                    L[i].pb(e);
                    temp.insert(e);
                }
            }
        }
    }
    rep(i, sz(child)) {
        dfs(child[i], L[i]);
    }
}

void Detect(int T, int n) {
    rep(i, n) reorder[i] = i;
    random_shuffle(reorder + 1, reorder + n);
    N = n;
    if(N == 2) Answer(1, 2);
    else if(T == 1) {
        rep(j, N) rep(i, j) {
            rep(k, N) place[k] = 0;
            place[i] = place[j] = 1;
            if(Ask(i, j, place)) Answer(i, j);
        }
    }
    else if(T == 2) {
        vector <int> v;
        for(int i=1;i<N-1;i++) v.pb(i);
        random_shuffle(all(v));
        Do_2(v);
        myAnswer_2(0, v[0]);
        myAnswer_2(v.back(), N - 1);
    }
    else if(T == 3) {
        vector <int> v; for(int i=1;i<N;i++) v.pb(i);
        dfs(0, v);
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 2128 KB Output is correct
2 Correct 116 ms 2128 KB Output is correct
3 Correct 119 ms 2128 KB Output is correct
4 Correct 206 ms 2128 KB Output is correct
5 Correct 176 ms 2128 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 2384 KB Output is correct
2 Correct 283 ms 2380 KB Output is correct
3 Correct 193 ms 2384 KB Output is correct
4 Correct 189 ms 2380 KB Output is correct
5 Correct 179 ms 2260 KB Output is correct
6 Correct 189 ms 2260 KB Output is correct
7 Correct 219 ms 2376 KB Output is correct
8 Correct 203 ms 2260 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2128 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 2128 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -