Submission #7852

#	Time	Username	Problem	Language	Result	Execution time	Memory
7852		ainu7	행성 탐사 (GA8_planet)	C++98	100 / 100	728 ms	2768 KiB

planet

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
#include "planet.h"
using namespace std;

const int trial = 101;
int px[trial], py[trial];

const int max_dup = 6;
int ax[trial][max_dup+2], ay[trial][max_dup+2]; // occ
int bx[trial][trial], by[trial][trial]; // real value

void ainta_init() {
  // init. subject to change according to performance.
  for (int i=0; i<57; i++)
    px[i] = py[i] = i;
  // 7-3-2-1
  px[57] = 0; py[57] = 57;
  px[58] = 1; py[58] = 58;
  px[59] = 2; py[59] = 59;
  px[60] = 3; py[60] = 60;
  px[61] = 4; py[61] = 61;
  px[62] = 5; py[62] = 62;
  px[63] = 6; py[63] = 63;
  px[64] = 0; py[64] = 64;
  px[65] = 1; py[65] = 65;
  px[66] = 2; py[66] = 66;
  px[67] = 0; py[67] = 67;
  px[68] = 1; py[68] = 68;
  px[69] = 0; py[69] = 69;
  for (int i=70; i<89; i++) {
    px[i] = i - 13;
    py[i] = i;
  }
  // 8-3-1
  px[89] = 76; py[89] = 0;
  px[90] = 77; py[90] = 1;
  px[91] = 78; py[91] = 2;
  px[92] = 79; py[92] = 3;
  px[93] = 80; py[93] = 4;
  px[94] = 81; py[94] = 5;
  px[95] = 82; py[95] = 6;
  px[96] = 83; py[96] = 7;
  px[97] = 84; py[97] = 0;
  px[98] = 85; py[98] = 1;
  px[99] = 86; py[99] = 2;
  px[100] = 87; py[100] = 0;

  int cx[trial] = {0}, cy[trial] = {0};
  for (int i=0; i<trial; i++) {
    if (px[i] && cx[px[i]-1] <= cx[px[i]]) {
      fprintf(stderr, "init error x %d\n", i);
      while (1);
    }
    if (py[i] && cy[py[i]-1] <= cy[py[i]]) {
      fprintf(stderr, "init error y %d\n", i);
      while (1);
    }
    cx[px[i]] ++;
    cy[py[i]] ++;
    if (cx[px[i]] > max_dup || cy[py[i]] > max_dup) {
      fprintf(stderr, "dup exceed %d\n", i);
      while (1);
    }
    for (int j=0; j<trial; j++) {
      bx[i][j] = cx[j];
      by[i][j] = cy[j];
      for (int k=1; k<=cx[j]; k++)
        ax[i][k] ++;
      for (int k=1; k<=cy[j]; k++)
        ay[i][k] ++;
    }
  }
}

void ainta() {
  static int q = 0;
  if (!q) { ainta_init(); q = 1; }

  for (int i=0; i<trial; i++)
    paint(px[i], py[i]);
}

int decision_x[trial * 2 + 9][trial+1];
int decision_y[trial * 2 + 9][trial+1];
int res_x[trial * 2 + 9][trial+1];
int res_y[trial * 2 + 9][trial+1];

pair<int, int> get_decision_x(int idx, int step) {
  if (step == 1) {
    res_x[idx][step] = 0;
    return pair<int, int>(0, 0);
  }

  if (decision_x[idx][step]) return pair<int, int>(decision_x[idx][step] - 1, res_x[idx][step]);
  int p[max_dup+2] = {0};
  int res_min = 999, prev = 0, decision = -1;
  for (int i=0; i<step; i++) {
    pair<int, int> res_ret = get_decision_x(idx+1, step-i-1);
    int res = res_ret.second + 1;

    int target = ++p[bx[min(trial-1, idx)][i]];
    if (target == step) break;
    pair<int, int> now_ret = get_decision_x(idx+1, target);
    int now = now_ret.second + 1;
    prev = max(prev, now);
    res = max(res, prev);

    if (res < res_min) {
      res_min = res;
      decision = i;
    }
  }
  decision_x[idx][step] = decision + 1;
  res_x[idx][step] = res_min;
  return pair<int, int>(decision, res_min);
}

pair<int, int> get_decision_y(int idx, int step) {
  if (step == 1) {
    res_y[idx][step] = 0;
    return pair<int, int>(0, 0);
  }

  if (decision_y[idx][step]) return pair<int, int>(decision_y[idx][step] - 1, res_y[idx][step]);
  int p[max_dup+2] = {0};
  int res_min = 999, prev = 0, decision = -1;
  for (int i=0; i<step; i++) {
    pair<int, int> res_ret = get_decision_y(idx+1, step-i-1);
    int res = res_ret.second + 1;

    int target = ++p[by[min(trial-1, idx)][i]];
    if (target == step) break;
    pair<int, int> now_ret = get_decision_y(idx+1, target);
    int now = now_ret.second + 1;
    prev = max(prev, now);
    res = max(res, prev);

    if (res < res_min) {
      res_min = res;
      decision = i;
    }
  }
  decision_y[idx][step] = decision + 1;
  res_y[idx][step] = res_min;
  return pair<int, int>(decision, res_min);
}

void sangsoo() {
  int idx = 0;
  const int len = 2222;

  int x_start = 0, x_step = len;
  while (x_step > ax[idx][1]) {
    int cr = ax[idx][1];
    int a = count_row(x_start + cr - 1);
    if (a) {
      x_step = cr;
      idx ++;
      break;
    }
    x_start += cr;
    x_step -= cr;
    idx ++;
  }
  while (x_step > 1) {
    pair<int, int> a_ret = get_decision_x(idx, x_step);
    int a = a_ret.first;
    int b = count_row(x_start + a);
    if (b == 0) {
      x_start += a+1;
      x_step -= a+1;
    } else {
      int prev_start = x_start;
      x_start = x_start + a - ax[idx][b] + 1;
      x_step = ax[idx][b] - ax[idx][b+1];
      int margin = max(0, prev_start - x_start);
      x_start += margin;
      x_step -= margin;
    }
    idx ++;
  }
  int y_start = 0, y_step = len;
  while (y_step > ay[idx][1]) {
    int cr = ay[idx][1];
    int a = count_col(y_start + cr - 1);
    if (a) {
      y_step = cr;
      idx ++;
      break;
    }
    y_start += cr;
    y_step -= cr;
    idx ++;
  }
  while (y_step > 1) {
    pair<int, int> a_ret = get_decision_y(idx, y_step);
    int a = a_ret.first;
    int b = count_col(y_start + a);
    if (b == 0) {
      y_start += a+1;
      y_step -= a+1;
    } else {
      int prev_start = y_start;
      y_start = y_start + a - ay[idx][b] + 1;
      y_step = ay[idx][b] - ay[idx][b+1];
      int margin = max(0, prev_start - y_start);
      y_start += margin;
      y_step -= margin;
    }
    idx ++;
  }

  report(x_start, y_start);
}

• Subtask 1: 40 / 40
• Subtask 2: 60 / 60