QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#32617#866. Display of SpringsAutumnKiteTL 0ms3536kbC++171.9kb2022-05-22 13:24:452022-05-22 13:24:46

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-22 13:24:46]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3536kb
  • [2022-05-22 13:24:45]
  • 提交

answer

#include <bits/stdc++.h>

const int LIM = 6;

int compare(int i, int j, int x) {
  std::cout << "? " << i << " " << j << " " << x << std::endl;
  std::string tmp;
  std::cin >> tmp;
  if (tmp == "FIRST") {
    return 1;
  } else if (tmp == "SECOND") {
    return -1;
  } else {
    return 0;
  }
}

class lichao_tree {
  struct node {
    node *ls, *rs;
    int id;

    node(int t_id) : ls(), rs(), id(t_id) {}
  };

  node *rt;

  void insert(node *&u, int l, int r, int id) {
    if (u == nullptr) {
      u = new node(id);
      return;
    }
    if (l == r) {
      if (compare(id, u->id, l) > 0) {
        u->id = id;
        return;
      }
    }
    int mid = (l + r) >> 1;
    if (compare(id, u->id, mid) > 0) {
      std::swap(id, u->id);
    }
    if (compare(id, u->id, l) > 0) {
      insert(u->ls, l, mid, id);
    } else {
      insert(u->rs, mid + 1, r, id);
    }
  }

  int query(node *u, int l, int r, int x) {
    if (u == nullptr) {
      return -1;
    }
    if (l == r) {
      return u->id;
    }
    int mid = (l + r) >> 1;
    int res;
    if (x <= mid) {
      res = query(u->ls, l, mid, x);
    } else {
      res = query(u->rs, mid + 1, r, x);
    }
    if (res == -1 || compare(u->id, res, x) > 0) {
      return u->id;
    } else {
      return res;
    }
  }

public:
  lichao_tree(int n) : rt() {
    for (int i = 0; i < n; ++i) {
      insert(rt, 1, LIM, i);
    }
    std::cout << "!" << std::endl;
  }

  void query(int x) {
    int res = query(rt, 1, LIM, x);
    std::cout << "! " << res << std::endl;
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n;
  std::cin >> n;
  lichao_tree T(n);
  while (true) {
    std::string tmp;
    std::cin >> tmp;
    if (tmp == "FINISH") {
      return 0;
    }
    int x;
    std::cin >> x;
    T.query(x);
  }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3536kb

input:

3
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
QUESTION 2
QUESTION 6
FIRST
SECOND
FINISH

output:

? 1 0 3
? 0 1 1
? 2 1 3
? 2 1 1
? 2 0 5
? 0 2 4
!
! 1
? 2 0 6
? 1 2 6
! 2

result:

ok Correct answer

Test #2:

score: -100
Time Limit Exceeded

input:

6
FIRST
EQUAL
FIRST
FIRST
EQUAL
SECOND
FIRST
SECOND
SECOND
SECOND
FIRST
EQUAL
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
QUESTION 1
SECOND
QUESTION 2
EQUAL
QUESTION 3
FIRST
QUESTION 4
SECOND
QUESTION 5
SECOND
QUESTION 6
FIRST
SECOND
QUESTION 7
FIRST
SECOND
QUESTION 10
FIRST
SECOND
QUESTI...

output:

? 1 0 3
? 0 1 1
? 2 1 3
? 1 2 1
? 3 2 3
? 3 2 1
? 3 0 5
? 0 3 4
? 4 2 3
? 4 2 1
? 4 3 5
? 3 4 4
? 3 0 6
? 5 2 3
? 5 2 1
? 5 4 5
? 5 4 4
? 5 3 6
? 5 3 6
? 5 3 6
!
? 2 1 1
! 1
? 2 1 2
! 1
? 2 1 3
! 2
? 2 4 4
! 4
? 2 4 5
! 4
? 4 3 6
? 2 4 6
! 4
? 4 3 7
? 2 4 7
! 4
? 4 3 10
? 2 4 10
! 4
? 4 3 1000
? 2 4...

result: