제출 #1067293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1067293		slivajan	Fire (BOI24_fire)	C++17	100 / 100	351 ms	43056 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long un;
typedef vector<un> vuc;
typedef pair<un, un> pun;

#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()
#define DEB(x) cerr << #x << " = " << (x) << endl;


int main(){
    un N, M;
    cin >> N >> M;

    vec<pun> vstup;
    map<un, un> mapa;

    REP(i, 0, N){
        un a, b;
        cin >> a >> b;
        vstup.push_back({a, b});
        mapa[a] = 0;
        mapa[b] = 0;
    }


    vuc imapa;
    un counter = 0;
    FEAC(kv, mapa){
        un key;
        tie(key, ignore) = kv;
        mapa[key] = counter;
        counter++;

        imapa.push_back(key);

    }

    sort(ALL(vstup));

    un K = imapa.size();
    vuc delky(K, 0);


    FEAC(kd, vstup){
        un key, destination;
        tie(key, destination) = kd;
        
        delky[mapa[key]] = (M+destination-key) % M;
    }

    un curr = 0;
    REP(ign, 0, 2){
        REP(i, 0, K){
            curr -= (M+imapa[i] - imapa[(K+i-1)%K]) % M;
            curr = max(curr, delky[i]);
            delky[i] = curr;
        }
    }

    vuc visited(K, 0);

    un ptr = 0;
    un time = 1;
    while(not visited[ptr]){
        visited[ptr] = time;
        if (delky[ptr] == 0) {
            cout << -1 << endl;
            return 0;
        }
        ptr = mapa[(imapa[ptr] + delky[ptr]) % M];
        time++;
    }

    un ret = 2;
    un goal = ptr;
    ptr = mapa[(imapa[ptr] + delky[ptr]) % M];
    un next_ptr = mapa[(imapa[ptr] + delky[ptr]) % M];

    while(((M + imapa[goal] - imapa[ptr]) % M) + ((M + imapa[next_ptr] - imapa[goal]) % M) >= M){
        ptr = next_ptr;
        next_ptr = mapa[(imapa[ptr] + delky[ptr]) % M];
        ret++;
    }

    cout << ret << endl;

}

• Subtask 1: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 13 / 13
• Subtask 5: 21 / 21
• Subtask 6: 26 / 26