oj.uz

Submission #721862

# Submission time Handle Problem Language Result Execution time Memory
721862 2023-04-11T08:01:09 Z joelgun14 Strange Device (APIO19_strange_device) C++17
5 / 100
 815 ms 67028 KB 
#include <bits/stdc++.h>
#define ll long long
#define lll __int128
#define endl "\n"
using namespace std;
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n, a, b;
    cin >> n >> a >> b;
    /*
    for(int i = 1; i <= n; ++i) {
        ll l, r;
        cin >> l >> r;
        for(int j = l; j <= r; ++j) {
            cout << (j + j / b) % a << " " << j % b << endl;
        }
    }
    */
    //return 0;
    // a or b has certain pattern
    // ab -> 1 cycle, no duplikat
    // next cycle: sama persis
    // maintain cycles in terms of ab, merge all segments
    // find modulo ab
    // exist more than one cycle long -> all possible
    // size ab berarti diff >= ab - 1
    vector<pair<lll, int>> sweep;
    ll ans = -1;
    lll tot;
    if(a == b + 1)
        tot = b;
    else if(b >= a)
        tot = (lll)a * b;
    else
        tot = (lll)a * b / gcd(a, b);
    // t + floor(t/b)
    // every a * b reset (pasti)
    for(int i = 1; i <= n; ++i) {
        ll l, r;
        cin >> l >> r;
        if(r - l >= tot - 1) {
            ans = tot;
        }
        else {
            if(tot <= 1e18) {
                l = (l % tot);
                r = (r % tot);
            }
            if(l <= r) {
                sweep.push_back(make_pair(l, 0));
                sweep.push_back(make_pair(r, 1));
            }
            else {
                sweep.push_back(make_pair(l, 0));
                sweep.push_back(make_pair(tot - 1, 1));
                sweep.push_back(make_pair(0, 0));
                sweep.push_back(make_pair(r, 1));
            }
        }
    }
    if(ans != -1)
        cout << ans << endl, exit(0);
    sort(sweep.begin(), sweep.end());
    int cnt = 0;
    ll st = -5;
    ans = 0;
    for(auto i : sweep) {
        if(i.second) {
            // end
            --cnt;
            if(cnt == 0)
                ans += i.first - st;
        }
        else {
            // start
            // start itu + cnt
            // set start kalo belum di set
            if(cnt == 0)
                st = i.first - 1;
            ++cnt;
        }
    }
    cout << ans << endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 1492 KB Output is correct
3 Correct 6 ms 1472 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 605 ms 66084 KB Output is correct
3 Incorrect 570 ms 67028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 605 ms 66084 KB Output is correct
3 Incorrect 570 ms 67028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 605 ms 66084 KB Output is correct
3 Incorrect 570 ms 67028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 65 ms 9676 KB Output is correct
3 Correct 72 ms 9492 KB Output is correct
4 Correct 815 ms 66120 KB Output is correct
5 Correct 79 ms 9572 KB Output is correct
6 Correct 73 ms 9564 KB Output is correct
7 Correct 77 ms 9528 KB Output is correct
8 Correct 70 ms 9404 KB Output is correct
9 Correct 70 ms 9620 KB Output is correct
10 Correct 69 ms 9472 KB Output is correct
11 Correct 67 ms 9560 KB Output is correct
12 Correct 63 ms 9580 KB Output is correct
13 Correct 85 ms 9496 KB Output is correct
14 Correct 736 ms 66160 KB Output is correct
15 Incorrect 74 ms 9572 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 1492 KB Output is correct
3 Correct 6 ms 1472 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -