oj.uz

Submission #60386

# Submission time Handle Problem Language Result Execution time Memory
60386 2018-07-24T04:39:39 Z 노영훈(#1742) Park (JOI17_park) C++11
20 / 100
 451 ms 1024 KB 
#include "park.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <utility>
#include <assert.h>
#include <map>
using namespace std;
typedef pair<int, int> pii;

static int full[1400], empt[1400];

void add_edge(int x, int y){
    if(x>y) swap(x,y);
    assert(x!=y);
    Answer(x,y);
}
int my_ask(int a, int b, int Arr[]){
    if(a>b) swap(a,b);
    assert(a!=b && Arr[a] && Arr[b]);
    return Ask(a,b,Arr);
}

void solve1(int n){
    int P[250]={};
    for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++){
            P[i]=P[j]=1;
            if(my_ask(i,j,P)) Answer(i,j);
            P[i]=P[j]=0;
        }
}

vector<int> dnc(int s, int e){
    // cout<<s<<' '<<e<<'\n';
    if(e<s){ vector<int> res; return res; }
    if(s==e){ vector<int> res={s}; return res; }
    int m=(s+e)/2;
    vector<int> A=dnc(s,m), B=dnc(m+1,e);
    vector<int> R;
    R.resize(A.size()+B.size());
    merge(A.begin(), A.end(), B.begin(), B.end(), R.begin(), [&](int a, int b){
        if(a==b) return true;
        full[b]=0; int now=my_ask(0,a,full); full[b]=1;
        return now!=0;
    });
    return R;
}

void solve2(int n){
    if(n==2) {Answer(0,1); return;}
    vector<int> ans=dnc(1,n-2);

    add_edge(0, ans[0]);
    for(int i=1; i<(int)ans.size(); i++) add_edge(ans[i-1], ans[i]);
    add_edge(ans.back(), n-1);
}

void dfs(int v, vector<int> &G){
    if(G.empty()) return;
    for(int x:G){
        empt[x]=1, empt[v]=1;
        int dir=my_ask(x,v,empt);
        empt[x]=0, empt[v]=0;
        if(!dir) continue;

        add_edge(x,v);

        vector<int> H;
        for(int y:G){
            if(x==y) continue;
            full[x]=0;
            int out=my_ask(0,y,full);
            full[x]=1;
            if(!out) H.push_back(y);
        }
        dfs(x,H);
    }
}

void solve3(int n){
    vector<int> V;
    for(int i=1; i<n; i++) V.push_back(i);
    dfs(0,V);
}

void Detect(int T, int n) {
    for(int i=0; i<n; i++) full[i]=1;
    if(T==1) solve1(n);
    if(T==2) solve2(n);
    if(T==3) solve3(n);
    if(T==4) solve3(n);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 15 ms 376 KB Output is correct
3 Correct 10 ms 420 KB Output is correct
4 Correct 11 ms 500 KB Output is correct
5 Correct 13 ms 708 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 764 KB Output is correct
2 Correct 66 ms 808 KB Output is correct
3 Correct 58 ms 836 KB Output is correct
4 Correct 156 ms 968 KB Output is correct
5 Correct 159 ms 968 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 968 KB Output is correct
2 Incorrect 451 ms 1024 KB Wrong Answer[5]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 271 ms 1024 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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