Submission #107099

#	Time	Username	Problem	Language	Result	Execution time	Memory
107099		thebes	Park (JOI17_park)	C++14	47 / 100	148 ms	632 KiB

park

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 0 / 30
• Subtask 5: 0 / 23