RUPC 2016 Day3 D: Complex Oracle (O(N^2) 解法)

問題

AIZU ONLINE JUDGE

解法

vector::erase() が速いこと、 vector::erase() を落とすテストケースが用意されていないこと、AOJが速いこと、N*2 クエリ用の時間のうちNクエリ分を計算時間として使えること等の様々な要因から、O(N^2)解法が通る。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
  if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}
template <class T, class U>
void chmin(T &t, U f) {
  if (t > f) t = f;
}
template <class T, class U>
void chmax(T &t, U f) {
  if (t < f) t = f;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<int> point(N, 0);

  printf("? %d %d\n", 1, N);
  fflush(stdout);
  ll prev;
  cin >> prev;
  for (int i = 1; i < N; ++i) {
    printf("? %d %d\n", (i + 1), N);
    fflush(stdout);

    ll resp;
    cin >> resp;
    ll diff = prev - resp;
    point[i - 1] = diff;
    prev = resp;
  }

  vector<int> v(N);
  for (int i = 0; i < N; ++i) v[i] = i + 1;

  printf("!");
  for (int i = 0; i < N; ++i) {
    printf(" %d", (v[point[i]]));
    v.erase(v.begin() + point[i]);
  }
  printf("\n");
  fflush(stdout);
}