oj.uz

Submission #107099

# Submission time Handle Problem Language Result Execution time Memory
107099 2019-04-22T00:50:01 Z thebes Park (JOI17_park) C++14
47 / 100
 148 ms 632 KB 
#include <bits/stdc++.h>
#include "park.h"
using namespace std;

int *arr;
bool cmp(int i,int j){
    int heh;
    arr[i]=0;
    if(Ask(0,j,arr)) heh = 0;
    else heh = 1;
    arr[i]=1;
    return heh;
}
void Detect(int T, int N){
    arr = (int*)malloc(N*sizeof(int));
    if(T==1){
        for(int i=0;i<N;i++){
            for(int j=i+1;j<N;j++){
                arr[i]=arr[j]=1;
                if(Ask(i,j,arr)) Answer(i,j);
                arr[i]=arr[j]=0;
            }
        }
    }
    else if(T==2){
        for(int i=0;i<N;i++) arr[i]=1;
        int lol[2000];
        for(int i=1;i<N-1;i++) lol[i-1]=i;
        sort(lol,lol+N-2,cmp);
        Answer(0,lol[0]);
        for(int i=0;i<N-3;i++) Answer(min(lol[i],lol[i+1]),max(lol[i],lol[i+1]));
        Answer(lol[N-3],N-1);
    }
    else if(T==3){
        int mrk[2000], par[2000];
        memset(mrk,0,sizeof(mrk));
        memset(par,0,sizeof(par));
        mrk[0] = 1; par[0] = -1;
        vector<int> a, b;
        a.push_back(0);
        for(int i=0;i<N;i++) arr[i]=0;
        for(int i=1;i<N;i++){
            arr[i]=1; arr[0]=1;
            if(Ask(0,i,arr)){
                mrk[i]=1; par[i]=0;
                b.push_back(i);
            }
            arr[i]=0; arr[0]=0;
        }
        swap(a,b);
        while(1){
            for(auto v : b) arr[v]=1;
            b.clear(); int lol = 0;
            for(int i=0;i<N;i++){
                if(mrk[i]) continue;
                for(auto v : a) arr[v]=1;
                arr[i]=1;
                if(!Ask(0,i,arr)){
                    arr[i]=0;
                    for(auto v : a) arr[v]=0;
                    continue;
                }
                for(auto v : a) arr[v]=0;
                arr[i]=0;
                lol = 1;
                int lo=0, hi=a.size();
                while(lo<hi){
                    int m = lo+hi>>1;
                    for(int i=0;i<=m;i++){
                        arr[a[i]]=1;
                    }
                    arr[i]=1;
                    if(Ask(0,i,arr)) hi=m;
                    else lo=m+1;
                    arr[i]=0;
                    for(int i=0;i<=m;i++){
                        arr[a[i]]=0;
                    }
                }
                if(lo!=a.size()){
                    par[i]=a[lo];
                    b.push_back(i);
                    mrk[i]=1;
                }
            }
            swap(a,b);
            if(!lol) break;
        }
        for(int i=1;i<N;i++){
            Answer(min(par[i],i),max(par[i],i));
        }
    }
}

Compilation message

park.cpp: In function 'void Detect(int, int)':
park.cpp:68:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     int m = lo+hi>>1;
                             ~~^~~
park.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(lo!=a.size()){
                    ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 8 ms 384 KB Output is correct
4 Correct 13 ms 384 KB Output is correct
5 Correct 8 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 632 KB Output is correct
2 Correct 92 ms 632 KB Output is correct
3 Correct 148 ms 604 KB Output is correct
4 Correct 147 ms 512 KB Output is correct
5 Correct 148 ms 512 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 384 KB Output is correct
2 Correct 94 ms 384 KB Output is correct
3 Correct 111 ms 508 KB Output is correct
4 Correct 83 ms 504 KB Output is correct
5 Correct 121 ms 256 KB Output is correct
6 Correct 94 ms 460 KB Output is correct
7 Correct 98 ms 488 KB Output is correct
8 Correct 117 ms 384 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
0 / 23.0

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