Submission #261730

#	Time	Username	Problem	Language	Result	Execution time	Memory
261730		yabsed	Cave (IOI13_cave)	C++17	100 / 100	1207 ms	760 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
    //printf("sdffsd %d \n", N);;
    int which_switch[N], how_switch[N], used[N], used_ans[N], used_for[N];
    memset(which_switch, 0, sizeof(which_switch));
    memset(how_switch, 0, sizeof(how_switch));
    memset(used, 0, sizeof(used));
    memset(used_ans, 0, sizeof(used_ans));
    memset(used_for, 0, sizeof(used_for));
    //printf("sdffsd %d \n", N);;
    for(int i=0;i<N;i++){
         //printf("sdffsd %d\n", i);;
        vector <int> p, np;

        int v[N];
        memset(v, 0, sizeof(v));
        for(int j=0;j<N;j++){
            //printf("%d", used[j]);
            if(!used[j])p.push_back(j);
            else np.push_back(j);
        }
        //printf("\n");
        int l=0, r=p.size()-1, mid;


        for(int j=0;j<np.size();j++)v[np[j]]=used_ans[np[j]];
        for(int j=0;j<p.size();j++)v[p[j]]=0;
        int res=tryCombination(v);
        if(res==i)how_switch[i]=1;
        else how_switch[i]=0;

        //printf("%d %d\n", i, how_switch[i]);
        while(l<r){
            mid=(l+r)/2;
            for(int j=0;j<np.size();j++)v[np[j]]=used_ans[np[j]];
            for(int j=0;j<=mid;j++)v[p[j]]=how_switch[i];
            for(int j=mid+1;j<p.size();j++)v[p[j]]=1-how_switch[i];
            int res=tryCombination(v);
            if(res==i)l=mid+1;
            else r=mid;
        }
        //printf("%d %d\n", l, r);
        which_switch[i]=p[l];
        used[p[l]]=1;
        used_ans[p[l]]=how_switch[i];
        used_for[p[l]]=i;

    }
    answer(used_ans, used_for);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<np.size();j++)v[np[j]]=used_ans[np[j]];
                     ~^~~~~~~~~~
cave.cpp:29:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<p.size();j++)v[p[j]]=0;
                     ~^~~~~~~~~
cave.cpp:37:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<np.size();j++)v[np[j]]=used_ans[np[j]];
                         ~^~~~~~~~~~
cave.cpp:39:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=mid+1;j<p.size();j++)v[p[j]]=1-how_switch[i];
                             ~^~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24