Submission #104825

#	Time	Username	Problem	Language	Result	Execution time	Memory
104825		CaroLinda	Cave (IOI13_cave)	C++14	0 / 100	936 ms	520 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 - 1 ;
    else u = mid + 1 ;
  }

  return l + 1 ;
}

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(resp1, resp2) ;

}

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