QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#32619#866. Display of SpringsAutumnKiteAC ✓143ms3696kbC++171.9kb2022-05-22 13:38:272022-05-22 13:38:28

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:38:28]
  • 评测
  • 测评结果:AC
  • 用时:143ms
  • 内存:3696kb
  • [2022-05-22 13:38:27]
  • 提交

answer

#include <bits/stdc++.h>

const int LIM = 100000;

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: 4ms
memory: 3596kb

input:

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

output:

? 1 0 50000
? 0 1 1
? 2 1 50000
? 1 2 1
!
? 2 1 2
! 1
? 2 1 6
! 2

result:

ok Correct answer

Test #2:

score: 0
Accepted
time: 9ms
memory: 3544kb

input:

6
FIRST
EQUAL
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
QUESTION 1
SECOND
SECOND
SECOND
SECOND
QUESTION 2
EQUAL
SECOND
SECOND
SECOND
QUESTION 3
FIRST
EQUAL
SECOND
SECOND
QUESTION 4
FIRST
FIRST
EQUAL
SECOND
QUESTION 5
FIRST...

output:

? 1 0 50000
? 0 1 1
? 2 1 50000
? 1 2 1
? 3 2 50000
? 2 3 1
? 2 1 25000
? 1 2 1
? 4 3 50000
? 3 4 1
? 3 2 25000
? 2 3 1
? 2 1 12500
? 1 2 1
? 5 4 50000
? 4 5 1
? 4 3 25000
? 3 4 1
? 3 2 12500
? 2 3 1
? 2 1 6250
? 1 2 1
!
? 2 1 1
? 3 1 1
? 4 1 1
? 5 1 1
! 1
? 2 1 2
? 3 1 2
? 4 1 2
? 5 1 2
! 1
? 2 1 3...

result:

ok Correct answer

Test #3:

score: 0
Accepted
time: 79ms
memory: 3528kb

input:

326
SECOND
SECOND
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
FIR...

output:

? 1 0 50000
? 1 0 1
? 2 0 50000
? 2 0 1
? 3 0 50000
? 0 3 1
? 0 2 25000
? 2 0 1
? 4 3 50000
? 4 3 1
? 4 0 25000
? 4 0 1
? 4 2 12500
? 2 4 1
? 5 3 50000
? 5 3 1
? 5 1 75000
? 5 1 50001
? 6 3 50000
? 6 3 1
? 6 0 25000
? 6 0 1
? 7 3 50000
? 7 3 1
? 7 0 25000
? 7 0 1
? 7 6 37500
? 7 6 25001
? 8 3 50000
...

result:

ok Correct answer

Test #4:

score: 0
Accepted
time: 14ms
memory: 3588kb

input:

19
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECON...

output:

? 1 0 50000
? 0 1 1
? 2 1 50000
? 2 1 1
? 2 0 75000
? 0 2 50001
? 3 1 50000
? 3 1 1
? 3 2 75000
? 2 3 50001
? 2 0 87500
? 0 2 75001
? 4 1 50000
? 4 1 1
? 4 3 75000
? 4 3 50001
? 4 2 87500
? 4 2 75001
? 4 0 93750
? 4 0 87501
? 5 1 50000
? 5 1 1
? 5 3 75000
? 5 3 50001
? 5 2 87500
? 5 2 75001
? 5 0 93...

result:

ok Correct answer

Test #5:

score: 0
Accepted
time: 105ms
memory: 3532kb

input:

500
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
F...

output:

? 1 0 50000
? 0 1 1
? 2 1 50000
? 1 2 1
? 1 0 75000
? 0 1 50001
? 3 2 50000
? 2 3 1
? 2 1 75000
? 1 2 50001
? 1 0 87500
? 0 1 75001
? 4 3 50000
? 4 3 1
? 4 2 75000
? 4 2 50001
? 4 1 87500
? 4 1 75001
? 4 0 93750
? 0 4 87501
? 5 3 50000
? 5 3 1
? 5 2 75000
? 5 2 50001
? 5 1 87500
? 5 1 75001
? 5 4 93...

result:

ok Correct answer

Test #6:

score: 0
Accepted
time: 141ms
memory: 3696kb

input:

500
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQ...

output:

? 1 0 50000
? 1 0 1
? 2 0 50000
? 2 0 1
? 2 1 75000
? 2 1 50001
? 3 0 50000
? 3 0 1
? 3 1 75000
? 3 1 50001
? 3 2 87500
? 3 2 75001
? 4 0 50000
? 4 0 1
? 4 1 75000
? 4 1 50001
? 4 2 87500
? 4 2 75001
? 4 3 93750
? 4 3 87501
? 5 0 50000
? 5 0 1
? 5 1 75000
? 5 1 50001
? 5 2 87500
? 5 2 75001
? 5 3 93...

result:

ok Correct answer

Test #7:

score: 0
Accepted
time: 113ms
memory: 3696kb

input:

500
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECON...

output:

? 1 0 50000
? 0 1 1
? 2 1 50000
? 2 1 1
? 2 0 75000
? 2 0 50001
? 3 1 50000
? 1 3 1
? 1 0 75000
? 0 1 50001
? 0 2 87500
? 2 0 75001
? 4 3 50000
? 4 3 1
? 4 1 75000
? 4 1 50001
? 4 0 87500
? 4 0 75001
? 4 2 93750
? 2 4 87501
? 5 3 50000
? 5 3 1
? 5 1 75000
? 5 1 50001
? 5 0 87500
? 5 0 75001
? 5 4 93...

result:

ok Correct answer

Test #8:

score: 0
Accepted
time: 143ms
memory: 3528kb

input:

500
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SEC...

output:

? 1 0 50000
? 1 0 1
? 2 0 50000
? 2 0 1
? 2 1 75000
? 1 2 50001
? 3 0 50000
? 3 0 1
? 3 2 75000
? 3 2 50001
? 3 1 87500
? 1 3 75001
? 4 0 50000
? 4 0 1
? 4 2 75000
? 4 2 50001
? 4 3 87500
? 4 3 75001
? 4 1 93750
? 1 4 87501
? 5 0 50000
? 5 0 1
? 5 2 75000
? 5 2 50001
? 5 3 87500
? 5 3 75001
? 5 4 93...

result:

ok Correct answer

Test #9:

score: 0
Accepted
time: 16ms
memory: 3548kb

input:

2
FIRST
FIRST
QUESTION 64500
QUESTION 22602
FIRST
QUESTION 37446
FIRST
QUESTION 97972
QUESTION 78630
QUESTION 75591
QUESTION 63328
QUESTION 64746
QUESTION 94532
QUESTION 51275
QUESTION 12189
FIRST
QUESTION 64341
QUESTION 85825
QUESTION 63713
QUESTION 36778
FIRST
QUESTION 27116
FIRST
QUESTION 18630
F...

output:

? 1 0 50000
? 0 1 1
!
! 1
? 1 0 22602
! 1
? 1 0 37446
! 1
! 1
! 1
! 1
! 1
! 1
! 1
! 1
? 1 0 12189
! 1
! 1
! 1
! 1
? 1 0 36778
! 1
? 1 0 27116
! 1
? 1 0 18630
! 1
! 1
? 1 0 28074
! 1
! 1
! 1
? 1 0 39195
! 1
! 1
? 1 0 1182
! 1
! 1
! 1
! 1
? 1 0 7017
! 1
? 1 0 13589
! 1
! 1
! 1
? 1 0 48324
! 1
! 1
! 1
...

result:

ok Correct answer

Test #10:

score: 0
Accepted
time: 23ms
memory: 3580kb

input:

2
FIRST
FIRST
QUESTION 54311
QUESTION 8466
SECOND
QUESTION 82055
QUESTION 65419
QUESTION 5271
SECOND
QUESTION 4799
SECOND
QUESTION 21521
FIRST
QUESTION 66767
QUESTION 24897
FIRST
QUESTION 69127
QUESTION 84527
QUESTION 23303
FIRST
QUESTION 88924
QUESTION 56421
QUESTION 88108
QUESTION 74033
QUESTION 2...

output:

? 1 0 50000
? 0 1 1
!
! 1
? 1 0 8466
! 0
! 1
! 1
? 1 0 5271
! 0
? 1 0 4799
! 0
? 1 0 21521
! 1
! 1
? 1 0 24897
! 1
! 1
! 1
? 1 0 23303
! 1
! 1
! 1
! 1
! 1
? 1 0 25348
! 1
? 1 0 10105
! 0
! 1
? 1 0 33359
! 1
? 1 0 49782
! 1
? 1 0 20392
! 1
! 1
! 1
? 1 0 4246
! 0
! 1
? 1 0 8620
! 0
? 1 0 30435
! 1
? 1...

result:

ok Correct answer

Test #11:

score: 0
Accepted
time: 122ms
memory: 3620kb

input:

500
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST...

output:

? 1 0 50000
? 1 0 1
? 2 0 50000
? 0 2 1
? 0 1 25000
? 1 0 1
? 3 2 50000
? 3 2 1
? 3 0 25000
? 0 3 1
? 0 1 12500
? 1 0 1
? 4 2 50000
? 2 4 1
? 2 3 25000
? 3 2 1
? 3 0 12500
? 0 3 1
? 0 1 6250
? 1 0 1
? 5 4 50000
? 5 4 1
? 5 2 25000
? 2 5 1
? 2 3 12500
? 3 2 1
? 3 0 6250
? 0 3 1
? 0 1 3125
? 1 0 1
? 6...

result:

ok Correct answer

Test #12:

score: 0
Accepted
time: 62ms
memory: 3556kb

input:

500
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
FIRST
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
SECOND
SECOND
FIRST
SECOND
FIRST
F...

output:

? 1 0 50000
? 0 1 1
? 2 1 50000
? 1 2 1
? 1 0 25000
? 0 1 1
? 3 2 50000
? 3 2 1
? 3 1 25000
? 1 3 1
? 1 0 12500
? 0 1 1
? 4 2 50000
? 4 2 1
? 4 3 25000
? 4 3 1
? 4 1 12500
? 1 4 1
? 5 2 50000
? 5 2 1
? 5 3 25000
? 5 3 1
? 5 4 12500
? 5 4 1
? 5 1 18750
? 1 5 12501
? 6 2 50000
? 6 2 1
? 6 3 25000
? 6 ...

result:

ok Correct answer

Test #13:

score: 0
Accepted
time: 95ms
memory: 3516kb

input:

500
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
FIRS...

output:

? 1 0 50000
? 0 1 1
? 2 1 50000
? 1 2 1
? 1 0 25000
? 0 1 1
? 3 2 50000
? 3 2 1
? 3 1 25000
? 3 1 1
? 3 0 12500
? 0 3 1
? 4 2 50000
? 4 2 1
? 4 1 25000
? 4 1 1
? 4 3 12500
? 4 3 1
? 4 0 6250
? 0 4 1
? 5 2 50000
? 5 2 1
? 5 1 25000
? 5 1 1
? 5 3 12500
? 5 3 1
? 5 4 6250
? 5 4 1
? 5 0 3125
? 5 0 1
? 6...

result:

ok Correct answer

Test #14:

score: 0
Accepted
time: 130ms
memory: 3620kb

input:

500
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
FIRST
FIRST
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
SECOND
FIRST
SECO...

output:

? 1 0 50000
? 0 1 1
? 2 1 50000
? 2 1 1
? 2 0 25000
? 0 2 1
? 3 1 50000
? 3 1 1
? 4 1 50000
? 4 1 1
? 4 2 25000
? 4 2 1
? 4 0 12500
? 0 4 1
? 5 1 50000
? 5 1 1
? 5 2 25000
? 5 2 1
? 5 4 12500
? 5 4 1
? 6 1 50000
? 6 1 1
? 6 2 25000
? 6 2 1
? 6 4 12500
? 6 4 1
? 6 5 18750
? 6 5 12501
? 7 1 50000
? 1 ...

result:

ok Correct answer

Test #15:

score: 0
Accepted
time: 75ms
memory: 3556kb

input:

500
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
SECOND
SECOND
FIR...

output:

? 1 0 50000
? 0 1 1
? 2 1 50000
? 1 2 1
? 1 0 25000
? 0 1 1
? 3 2 50000
? 3 2 1
? 3 1 25000
? 3 1 1
? 3 0 12500
? 0 3 1
? 4 2 50000
? 4 2 1
? 4 1 25000
? 4 1 1
? 4 3 12500
? 3 4 1
? 3 0 6250
? 0 3 1
? 5 2 50000
? 5 2 1
? 5 1 25000
? 5 1 1
? 5 4 12500
? 4 5 1
? 4 3 6250
? 3 4 1
? 3 0 3125
? 3 0 1
? 6...

result:

ok Correct answer

Test #16:

score: 0
Accepted
time: 77ms
memory: 3616kb

input:

500
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
SECOND
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
SECOND
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
S...

output:

? 1 0 50000
? 0 1 1
? 2 1 50000
? 2 1 1
? 2 0 25000
? 2 0 1
? 3 1 50000
? 3 1 1
? 3 0 25000
? 3 0 1
? 3 2 12500
? 2 3 1
? 4 1 50000
? 4 1 1
? 4 0 25000
? 4 0 1
? 4 3 12500
? 4 3 1
? 4 2 6250
? 2 4 1
? 5 1 50000
? 5 1 1
? 5 0 25000
? 5 0 1
? 5 3 12500
? 5 3 1
? 5 4 6250
? 4 5 1
? 6 1 50000
? 6 1 1
? ...

result:

ok Correct answer