제출 #173689

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
173689		FieryPhoenix	동굴 (IOI13_cave)	C++11	100 / 100	1299 ms	640 KiB

cave

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
#include "cave.h"
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

vector<int>ind;
int S[5001],D[5001];

void exploreCave(int N){
  for (int i=0;i<N;i++){
    S[i]=-1; D[i]=-1;
    ind.push_back(i);
  }
  for (int i=0;i<N;i++){ //figuring out door i now
    int v[5001];
    fill(v,v+N,1);
    for (int j=0;j<N;j++)
      if (S[j]!=-1)
	v[j]=D[j];
    int r=tryCombination(v);
    if (r==-1) r=INF;
    bool state;
    if (r>i)
      state=true;
    else
      state=false;
    int low=0,high=ind.size()-1,mid;
    while (low<high){
      mid=(low+high)/2;
      int q[5001];
      fill(q,q+N,0);
      for (int j=low;j<=mid;j++)
	q[ind[j]]=1;
      for (int j=0;j<N;j++)
	if (S[j]!=-1)
	  q[j]=D[j];
      int res=tryCombination(q);
      if (res==-1) res=INF;
      if (res>i){
	if (state)
	  high=mid;
	else
	  low=mid+1;
      }
      else{
	if (state)
	  low=mid+1;
	else
	  high=mid;
      }
    }
    S[ind[low]]=i;
    D[ind[low]]=state;
    ind.erase(ind.begin()+low);
  }
  answer(D,S);
}

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