제출 #109463

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
109463		Nucleist	Cave (IOI13_cave)	C++14	51 / 100	2098 ms	536 KiB

cave

#include <bits/stdc++.h> 
#include "cave.h"
using namespace std; 
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define pb push_back
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
int visited[5001];
int pos[5001];
int n;
map<string,int>gg;
void exploreCave(int n)
{
  memset(visited,-1,sizeof visited);
  int high=n;
  int low=0;
  int k = 0;
  int ans1=0,ans2=0;
  while(k!=n)
  {
    high=n-1;
    int tab[n]={0};
    low=0;
    while(true)
  {
    string kali;
    if(high == low && visited[low]==-1)
    {
      //debug(low);
      tab[high]=1;
      ans2 = tryCombination(tab);
      tab[low]=0;
      ans1 = tryCombination(tab);
      break;
    }
    else if(high==low){/*debug(low);*/break;}
   // debugs(high,low);
    int mid=((high+low)/2)+1;
    for (int i = 0; i < n; ++i)
    {
      if(visited[i]==-1)
        {tab[i]=0;}
      else {tab[i]=pos[i];}
      kali.pb((char)(tab[i]+48));
    }
    //debug(kali);
    /*if(gg.find(kali)!=gg.end())ans1=gg[kali];
    else gg[kali]=tryCombination(tab);
    ans1=gg[kali];*/
    ans1=tryCombination(tab);
    //kali.clear();
      //debugs(mid,high);
    for (int i = mid; i <= high; ++i)
    {
      //debugs(i,visited[i]);
      if(visited[i]==-1)
        tab[i]=1;
      else {tab[i]=pos[i];}
    }
    for (int i = 0; i < n; ++i)
    {
      kali.pb((char)(tab[i]+48));
    }
    /*debug(kali);
    if(gg.find(kali)!=gg.end())ans2=gg[kali];
    else gg[kali]=tryCombination(tab);
    ans2=gg[kali];*/
    ans2=tryCombination(tab);
    if(ans1==ans2)
    {
      high=mid-1;
    }
    else
    {
      low=mid;
    }
  }
  if(ans1==-1)ans1=n;
  if(ans2==-1)ans2=n;
  //debugs(low,min(ans1,ans2));
  visited[low]=min(ans2,ans1);
  if(ans1>ans2)
  {
    pos[low]=0;
  }
  else pos[low]=1;
  k++;
  }
  answer(pos,visited);
  return;
}

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