oj.uz

Submission #60378

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

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

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(Ask(i,j,P)) Answer(i,j);
            P[i]=P[j]=0;
        }
}

static int P2[1400];
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;
        P2[b]=0; int now=Ask(0,a,P2); P2[b]=1;
        return now!=0;
    });
    return R;
}

void solve2(int n){
    if(n==2) {Answer(0,1); return;}
    for(int i=0; i<n; i++) P2[i]=1;
    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 Detect(int T, int n) {
    if(T==1) solve1(n);
    if(T==2) solve2(n);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 9 ms 496 KB Output is correct
3 Correct 10 ms 608 KB Output is correct
4 Correct 11 ms 608 KB Output is correct
5 Correct 10 ms 608 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 760 KB Output is correct
2 Correct 71 ms 796 KB Output is correct
3 Correct 64 ms 796 KB Output is correct
4 Correct 161 ms 912 KB Output is correct
5 Correct 171 ms 916 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 23.0

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