Submission #283401

#	Time	Username	Problem	Language	Result	Execution time	Memory
283401		AlexLuchianov	Worm Worries (BOI18_worm)	C++14	59 / 100	873 ms	512 KiB

worm

#include <iostream>
#include <vector>
#include <cassert>
#include <random>
#include <chrono>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

std::mt19937 rng(std::chrono::high_resolution_clock::now().time_since_epoch().count());

int _rand(int from, int to) {
  return from + std::uniform_int_distribution<int>(0, to - from)(rng) % (to - from + 1);
}

int rand_except(int from, int to, int target) {
  int result = _rand(from, to);
  if(result != target)
    return result;
  else
    return rand_except(from, to, target);
}

int const nmax = 1000000;
int v[1 + nmax];

int n, m, k;
int valid(int x, int y, int z) {
  return 1 <= x && x <= n && 1 <= y && y <= m && 1 <= z && z <= k;
}
int ask(int x, int y, int z) {
  std::cout << "? " << x << " " << y << " " << z << '\n';
  //assert(valid(x, y, z));
  std::cout << std::flush;
  int val;
  std::cin >> val;
  return val;
}

int solve(int from, int to, int pos) {
  if(from == to)
    return pos;
  else {
    int pos2 = rand_except(from, to, pos);
    v[pos2] = ask(pos2, 1, 1);
    if(pos2 < pos)
      std::swap(pos, pos2);
    if(v[pos] < v[pos2])
      return solve(pos + 1, to, pos2);
    else
      return solve(from, pos2 - 1, pos);
  }
}

int const xplus[6] = {0, 0, -1, 1, 0, 0};
int const yplus[6] = {1, -1, 0, 0, 0, 0};
int const zplus[6] = {0, 0, 0, 0, 1, -1};


bool nxt(int &x, int &y, int &z, int &cost) {
  for(int h = 0; h < 6; h++) {
    int x2 = x + xplus[h];
    int y2 = y + yplus[h];
    int z2 = z + zplus[h];
    if(valid(x2, y2, z2)) {
      int cost2 = ask(x2, y2, z2); 
      if(cost < cost2) {
        x = x2;
        y = y2;
        z = z2;
        cost = cost2;
        return 1;
      }
    }
  }
  return 0;
}

int main() {
  
  int q;
  std::cin >> n >> m >> k >> q;
  if(q == 35) {
    int pos = _rand(1, n);
    v[pos] = ask(pos, 1, 1);
    int result =  solve(1, n, pos);
    std::cout << "! " << result << " " << 1 << " " << 1 << '\n';
  } else {
    int x, y, z, cost = 0;
    for(int i = 1;i <= q / 2; i++) {
      int x2 = _rand(1, n);
      int y2 = _rand(1, m);
      int z2 = _rand(1, k);
      int cost2 = ask(x2, y2, z2);
      assert(valid(x2, y2, z2));
      if(cost < cost2) {
        x = x2;
        y = y2;
        z = z2;
        cost = cost2;
      }
    }
    while(nxt(x, y, z, cost));
    std::cout << "! " << x << " " << y << " " << z << '\n';
    std::cout << std::flush;
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 22
• Subtask 3: 12 / 12
• Subtask 4: 0 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23