Submission #104833

#	Time	Username	Problem	Language	Result	Execution time	Memory
104833		CaroLinda	Cave (IOI13_cave)	C++14	100 / 100	1111 ms	640 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
 
#define MAXN 5005
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
 
using namespace std;
 
int N ;
int A[MAXN] , B[MAXN] , s[MAXN];
int resp1[MAXN] , resp2[MAXN] ;
pii ans[MAXN] ;
 
int findDoor( int door )
{
  memset(s , 0 , sizeof s) ;
 
  lp(i,0,N)
    if( A[i] != -1 ) s[ A[i] ] = B[i] ;
 
  int k = tryCombination(s) ;
  if(k == -1) k = door + 1 ;
  if( k > door ) return B[door] = 0 ;
  else return B[door] = 1 ;
}
 
int findSwitch( int door )
{
  int u = 0 , l = N-1 , mid ;
  int x = B[door] ;
 
  while( u < l )
  {
    mid = (u+l)/2 ;
    memset(s , -1 , sizeof s) ;
    lp(i,0,N)
      if(A[i] != -1) s[ A[i] ] = B[ i ] ;
    lp(i,u,mid+1)
      if(s[i] == -1 ) s[i] = x ;
    lp(i,mid+1 , l+1)
      if( s[i] == -1 ) s[i] = !x ;
   
    int k = tryCombination(s) ;
    if( k == -1 ) k = door + 1 ;
    if(k > door) l = mid ;
    else u = mid + 1 ;
  }
 
  return l  ;
}
 
void exploreCave( int n )
{
  //
  N = n ;
  memset(A, -1 , sizeof A) ;
  memset(B, -1, sizeof B) ;
  //
 
  lp(i,0,N)
  {
    B[i] = findDoor(i) ;
    A[i] = findSwitch(i) ;
  }
 
  pii p[MAXN] ;
  lp(i,0,N) p[i] = pii( A[i] , i ) ;
  sort(p,p+N) ;
 
  lp(i,0,N) resp1[i] = p[i].ss ;
  lp(i,0,N) resp2[i] = B[ p[i].ss ] ;
 
  answer(resp2, resp1) ;
 
}

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