oj.uz

답안 #60388

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60388 2018-07-24T04:44:15 Z 노영훈(#1742) Park (JOI17_park) C++11
47 / 100
 342 ms 1216 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;
    bool done[1400]={};
    for(int x:G){
        if(done[x]) continue;
        empt[x]=1, empt[v]=1;
        int dir=my_ask(x,v,empt);
        empt[x]=0, empt[v]=0;
        if(!dir) continue;

        done[x]=true;
        add_edge(x,v);

        vector<int> H;
        for(int y:G){
            if(done[y]) continue;
            full[x]=0;
            int out=my_ask(0,y,full);
            full[x]=1;
            if(out) continue;
            done[y]=true;
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 11 ms 376 KB Output is correct
3 Correct 10 ms 436 KB Output is correct
4 Correct 10 ms 488 KB Output is correct
5 Correct 16 ms 544 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 720 KB Output is correct
2 Correct 53 ms 720 KB Output is correct
3 Correct 64 ms 720 KB Output is correct
4 Correct 151 ms 720 KB Output is correct
5 Correct 141 ms 720 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 327 ms 720 KB Output is correct
2 Correct 329 ms 736 KB Output is correct
3 Correct 322 ms 780 KB Output is correct
4 Correct 242 ms 800 KB Output is correct
5 Correct 260 ms 836 KB Output is correct
6 Correct 342 ms 904 KB Output is correct
7 Correct 215 ms 924 KB Output is correct
8 Correct 293 ms 944 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 964 KB Output is correct
2 Incorrect 301 ms 1216 KB Wrong Answer[5]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 1216 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -