oj.uz

답안 #721548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
721548 2023-04-11T04:09:36 Z joelgun14 이상한 기계 (APIO19_strange_device) C++17
10 / 100
 612 ms 34548 KB 
#include <bits/stdc++.h>
#define ll long long
#define lll __int128
#define endl "\n"
using namespace std;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n, a, b;
    cin >> n >> a >> b;
    // 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<ll, bool>> sweep;
    ll ans = -1;
    for(int i = 1; i <= n; ++i) {
        ll l, r;
        cin >> l >> r;
        if(r - l >= (lll)1 * a * b) {
            ans = (lll)1 * a * b;
        }
        else {
            l %= (lll)1 * a * b;
            r %= (lll)1 * a * b;
            if(l <= r) {
                sweep.push_back(make_pair(l, 0));
                sweep.push_back(make_pair(r, 1));
            }
            else {
                sweep.push_back(make_pair(0, 0));
                sweep.push_back(make_pair(l, 0));
                sweep.push_back(make_pair(a * b - 1, 1));
                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;
    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;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:51:32: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |                 ans += i.first - st;
      |                        ~~~~~~~~^~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 856 KB Output is correct
3 Correct 5 ms 856 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 1 ms 316 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 343 ms 33244 KB Output is correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 496 ms 34128 KB Output is correct
3 Incorrect 461 ms 34548 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 496 ms 34128 KB Output is correct
3 Incorrect 461 ms 34548 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 496 ms 34128 KB Output is correct
3 Incorrect 461 ms 34548 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 51 ms 4528 KB Output is correct
3 Correct 52 ms 5296 KB Output is correct
4 Correct 612 ms 33232 KB Output is correct
5 Correct 53 ms 5320 KB Output is correct
6 Correct 53 ms 5236 KB Output is correct
7 Correct 54 ms 5252 KB Output is correct
8 Correct 53 ms 5244 KB Output is correct
9 Correct 53 ms 5312 KB Output is correct
10 Correct 55 ms 5200 KB Output is correct
11 Correct 52 ms 5224 KB Output is correct
12 Correct 52 ms 5268 KB Output is correct
13 Correct 58 ms 5308 KB Output is correct
14 Correct 585 ms 33252 KB Output is correct
15 Incorrect 54 ms 5312 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 856 KB Output is correct
3 Correct 5 ms 856 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -