QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#180828 | #6348. Egor Has a Problem | ucup-team859# | TL | 1ms | 3512kb | C++14 | 1.2kb | 2023-09-16 13:27:09 | 2023-09-16 13:27:09 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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...