QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#180828#6348. Egor Has a Problemucup-team859#TL 1ms3512kbC++141.2kb2023-09-16 13:27:092023-09-16 13:27:09

Judging History

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

  • [2023-09-16 13:27:09]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3512kb
  • [2023-09-16 13:27:09]
  • 提交

answer

#include <bits/stdc++.h>

#define lsb(x) (x & (-x))

using ull = unsigned long long;
using ll = long long;

using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<ll> a(n + 1, 0);
  for (int i = 1; i <= n; ++i)
    cin >> a[i];

  if (n <= 129) {
    for (int i = 1; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        for (int p = j + 1; p < n; ++p) {
          for (int q = p + 1; q <= n; ++q) {
            if (a[j] / a[i] == a[q] / a[p]) {
              cout << "YES\n";
              cout << i << " " << j << " " << p << " " << q << endl;
              return;
            }
          }
        }
      }
    }
  } else {
    map<ll, int> f;
    for (int i = 1; i < n; ++i) {
      ll x = a[i + 1] / a[i];
      if (f.count(x)) {
        cout << "YES\n";
        cout << f[x] << " " << f[x] + 1 << " " << i << " " << i + 1 << endl;
      }
      if (i - 1 > 0) {
        f[a[i] / a[i - 1]] = i - 1;
      }
    }
  }

  cout << "NO";
}

int main() {
#ifdef HOME
  ifstream cin("input.in");
  ofstream cout("output.out");
#endif
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  
  int t = 1;
  //cin >> t;
  while (t--)
    solve();

  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3512kb

input:

6
2 6 11 21 47 120

output:

YES
1 3 4 6

result:

ok OK

Test #2:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

5
1 2 6 30 210

output:

NO

result:

ok OK

Test #3:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

4
7 13 77 143

output:

YES
1 2 3 4

result:

ok OK

Test #4:

score: 0
Accepted
time: 1ms
memory: 3444kb

input:

4
10 29 31 100

output:

NO

result:

ok OK

Test #5:

score: -100
Time Limit Exceeded

input:

500000
627045176858 4817409059014 6288122580263 11138485427254 14292718094002 14799874839768 16926890883539 17617152313162 17645472255619 18208915248631 22963632241827 24466999302606 25551903318615 26091633648017 38200644379849 39885775205129 40036378248650 40309675851194 40773414900416 408933438176...

output:

YES
2 3 4 5
YES
3 4 5 6
YES
4 5 6 7
YES
5 6 7 8
YES
6 7 8 9
YES
7 8 9 10
YES
8 9 10 11
YES
9 10 11 12
YES
10 11 12 13
YES
11 12 13 14
YES
12 13 14 15
YES
13 14 15 16
YES
14 15 16 17
YES
15 16 17 18
YES
16 17 18 19
YES
17 18 19 20
YES
18 19 20 21
YES
19 20 21 22
YES
20 21 22 23
YES
21 22 23 24
YES
22...

result: