제출 #876516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876516		n3rm1n	동굴 (IOI13_cave)	C++17	0 / 100	395 ms	532 KiB

cave

#include<bits/stdc++.h>
#include "cave.h"
#define endl '\n'
using namespace std;
const int MAXN = 5005;

 /* #define MAX_N 5000
  #define MAX_CALLS 70000

  #define fail(s, x   ) do { \
  		fprintf(stderr, s "\n", ## x); \
  		exit(1); \
  	} while(0)


  #define N koala
  #define realS kangaroo
  #define realD possum
  #define inv platypus
  #define num_calls echidna

  static int N;
  static int realS[MAX_N];
  static int realD[MAX_N];
  static int inv[MAX_N];
  static int num_calls;

  void answer(int S[], int D[]) {
      int i;
      int correct = 1;
      for (i = 0; i < N; ++i)
          if (S[i] != realS[i] || D[i] != realD[i]) {
              correct = 0;
              break;
          }

      if (correct)
          printf("CORRECT\n");
      else
          printf("INCORRECT\n");

      for (i = 0; i < N; ++i) {
          if (i > 0)
              printf(" ");
          printf("%d", S[i]);
      }
      printf("\n");

      for (i = 0; i < N; ++i) {
          if (i > 0)
              printf(" ");
          printf("%d", D[i]);
      }
      printf("\n");

      exit(0);
  }
  int n;
  int tryCombination(int S[]) {
      int i;

      if (num_calls >= MAX_CALLS) {
          printf("INCORRECT\nToo many calls to tryCombination() \n");
          exit(0);
      }
      for(int i = 0;i < n;++i){
      	cout << S[i] << ' ';
      }
      cout << '\n';
      ++num_calls;

      for (i = 0; i < N; ++i)
          if (S[inv[i]] != realS[inv[i]])
              return i;
      return -1;
  }

  /*int init() {
      int i, res;

      FILE *f = fopen("cave in", "r");
  	if (!f)
  		fail("Failed to open input file ");

  	res = fscanf(f, "%d", &N);

      for (i = 0; i < N; ++i) {
          res = fscanf(f, "%d", &realS[i]);
    }
     for (i = 0; i < N; ++i) {
         res = fscanf(f, "%d", &realD[i]);
        inv[realD[i]] = i;
    }

     num_calls = 0;
     return N;
 }*/
int n, taken[MAXN], correct[MAXN], connected_to[MAXN];
int curr_try[MAXN];
void help_try_01(int mid)
{
    for (int i = 0; i < mid; ++ i)
        curr_try[i] = 0;
    for (int i = mid; i < n; ++ i)
        curr_try[i] = 1;
    for (int i = 0; i < n; ++ i)
    {
        if(taken[i])curr_try[i] = correct[i];
    }
}
void help_try_10(int mid)
{
    for (int i = 0; i < mid; ++ i)
        curr_try[i] = 1;
    for (int i = mid; i < n; ++ i)
        curr_try[i] = 0;
    for (int i = 0; i < n; ++ i)
    {
        if(taken[i])curr_try[i] = correct[i];
    }
}
void exploreCave(int N)
{
    n = N;
    for (int door = 0; door < n; ++ door)
    {
        if(tryCombination(correct) > door || tryCombination(correct) == -1)
        {
            int l = 0, r = n-1, mid, ans = -1;
            while(l <= r)
            {
                mid = (l + r)/2;
                help_try_01(mid);
                int res = tryCombination(curr_try);
                if(res >= door || res == -1)
                {
                    ans = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            taken[ans] = 1;
            correct[ans] = 0;
            connected_to[ans] = door;
        }
        else
        {
            int l = 0, r = n-1, mid, ans = -1;
            while(l <= r)
            {
                mid = (l + r)/2;
                help_try_10(mid);
                int res = tryCombination(curr_try);
                if(res >= door || res == -1)
                {
                    ans = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            taken[ans] = 1;
            correct[ans] = 1;
            connected_to[ans] = door;
        }
    }
    answer(correct, connected_to);
}
  /*int main()
  {
  	cin >> n;
  	for(int i = 0;i < n;++i){
  		cin >> realS[i];
  	}
  	for(int i = 0;i < n;++i){
  		cin >> realD[i];
  	}
  	exploreCave(n);
  }*/
/***
4
1 1 0 0
3 1 2 0
*/

컴파일 시 표준 에러 (stderr) 메시지

cave.cpp:78:3: warning: "/*" within comment [-Wcomment]
   78 |   /*int init() {
      |

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