QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#103568#6348. Egor Has a Problemgapinho#RE 270ms18568kbC++142.1kb2023-05-06 20:38:192023-05-06 20:38:20

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-06 20:38:20]
  • 评测
  • 测评结果:RE
  • 用时:270ms
  • 内存:18568kb
  • [2023-05-06 20:38:19]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long

using namespace std;

int ans[2][2];

void printAns() {
    for(int i = 0; i < 2; ++i) {
        for(int j = 0; j < 2; ++j) {
            cout << ans[i][j] + 1 << ' ';
        }
    }
    exit(0);
}

int32_t main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int &x : a) cin >> x;
    int ans[2][2];
    int z = 0;
    for(int i = 1; i < n && z < 2; ++i) {
        if(a[i] < a[i - 1]) {
            ans[z][0] = i - 1;
            ans[z][1] = i;
            z++;
            i++;
        }
    }
    if(z == 2) {
        cout << "YES\n";
        printAns();
    }
    if(n < 1000) {
        map<int, pair<int, int>> dic;
        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j < n; ++j) {
                if(dic.count(a[j]/a[i])) {
                    cout << "YES\n";
                    auto h = dic[a[j]/a[i]];
                    cout << h.first+1 << ' ' << h.second + 1 << ' ' << i + 1 << ' ' << j + 1 << endl;
                    return 0;
                }
            }
            for(int j = 0; j < i; j++) {
                dic[a[i]/a[j]] = make_pair(j, i);
            }
        }
        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";
    int quebra = 0;
    for(int i = 1; i < n; ++i) {
        if(a[i] < a[i - 1]) {
            quebra = i;
            break;
        }
    }
    vector<int> b;
    if(quebra < n / 2) {
        for(int i = quebra; i < n; ++i) {
            b.push_back(a[i]);
        }
    } else {
        for(int i = quebra - 1; i >= 0; --i) {
            b.push_back(a[i]);
        }
    }

    vector<vector<int>> bits(100, vector<int>());

    for(int i = 0; i < b.size(); ++i) {
        for(int j = 62; j >= 0; j--) {
            if(b[i] & (1ll << j)) {
                bits[j].push_back(i);
                break;
            }
        }
    }

    for(int i = 0; i < bits.size(); ++i) {
        if(bits[i].size() == 4) {
            for(int j = 0; j < 4; ++j) {
                cout << bits[i][j] + 1 << ' ';
            }
            exit(0);
        }
    }
    assert(false);
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3300kb

input:

6
2 6 11 21 47 120

output:

YES
1 3 4 6

result:

ok OK

Test #2:

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

input:

5
1 2 6 30 210

output:

NO

result:

ok OK

Test #3:

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

input:

4
7 13 77 143

output:

YES
1 2 3 4

result:

ok OK

Test #4:

score: 0
Accepted
time: 2ms
memory: 3308kb

input:

4
10 29 31 100

output:

NO

result:

ok OK

Test #5:

score: 0
Accepted
time: 245ms
memory: 17188kb

input:

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

output:

YES
4 5 6 7 

result:

ok OK

Test #6:

score: 0
Accepted
time: 266ms
memory: 17244kb

input:

500000
4296317198460 9088530306835 12761569474357 16261038279090 16941085611205 18350614838717 22480413215272 23329628179141 24312311764761 24433929342173 27221427530427 28176763451413 28796907935821 30472998712185 32522454545697 33716639435084 36803789739537 36820525380957 39761789956892 4078696306...

output:

YES
2 3 4 5 

result:

ok OK

Test #7:

score: 0
Accepted
time: 270ms
memory: 17256kb

input:

500000
2486629253945 2653364744556 4284488165789 4329370039939 4642065503681 6901749347495 19192137130640 21230142707219 21572527039148 22380596790669 24549580468932 24705234465366 24809017205084 25372640950744 30936948747149 31605133106641 35382503368540 36668459004194 39297585189262 40441705410326...

output:

YES
1 2 3 4 

result:

ok OK

Test #8:

score: 0
Accepted
time: 257ms
memory: 18568kb

input:

500000
1212707463644 3060808785468 5253681005592 6636218910647 8688761397981 9169130038833 9604296507161 10581672897486 14606712594653 18215478522408 19985113657583 21876858531698 22009681507073 25744252327149 29854713235059 30049643326503 35465827651805 38437058489989 40205415453241 42389564776077 ...

output:

YES
6 7 8 9 

result:

ok OK

Test #9:

score: -100
Dangerous Syscalls

input:

500000
1 999999999999500002 999999999999500003 999999999999500004 999999999999500005 999999999999500006 999999999999500007 999999999999500008 999999999999500009 999999999999500010 999999999999500011 999999999999500012 999999999999500013 999999999999500014 999999999999500015 999999999999500016 999999...

output:


result: