Submission #444179

#	Time	Username	Problem	Language	Result	Execution time	Memory
444179		Supersonic	Cave (IOI13_cave)	C++14	100 / 100	1085 ms	676 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> f;int s[5001];bool ts[5001];int n;
int fc(int a,int b,bool c){
   int sr[n];//cerr<<endl;
   for(int i=0;i<n;i++)sr[i]=(a<=i&&i<=b)?c:!c;
   for(int i=0;i<f.size();i++)sr[f[i]]=ts[i];
   //for(int i=0;i<n;i++)cerr<<sr[i]<<' ';cerr<<endl;
   //cerr<<tryCombination(sr)<<endl;
   return tryCombination(sr);
}
void exploreCave(int N) {
   //freopen("debug.out","w",stdout);
   n=N;//cout<<N<<endl;
   for(int i=0;i<n;i++){
      //cout<<i<<endl;
      memset(s,0,sizeof(s));
      int k=fc(0,n-1,0);
      if(k==i)ts[i]=1;
      else ts[i]=0;
      //cerr<<ts[i]<<endl;
      int a=0,b=n-1;
      while(a<=b){
         int m=(a+b)/2;
         k=fc(0,m,ts[i]);//cerr<<k<<' ';
         if(k==i)a=m+1;
         else b=m-1;
         if(k<i&&k>=0)exit(1);
      }//cerr<<endl;
      //cerr<<a<<endl;
      f.push_back(a);
   }
   int rd[n];int rs[n];
   for(int i=0;i<n;i++)rd[f[i]]=i;
   for(int i=0;i<n;i++)rs[i]=ts[rd[i]];
   answer(rs,rd);
}

Compilation message (stderr)

cave.cpp: In function 'int fc(int, int, bool)':
cave.cpp:8:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |    for(int i=0;i<f.size();i++)sr[f[i]]=ts[i];
      |                ~^~~~~~~~~

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