제출 #1355048

#제출 시각아이디문제언어결과실행 시간메모리
1355048AMel0nA String Problem (EGOI25_stringproblem)C++20
100 / 100
92 ms19452 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PRINT cout << "HERE" << endl
const int INF = 1e9+7;

int N, P;
vector<int> took, done;
vector<vector<pair<int,int>>> rot;
vector<pair<pair<int,int>, int>> str;
vector<int> atpin;
signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N;
    P = 2*N;
    rot.resize(P), took.resize(P), done.resize(N), str.resize(N), atpin.resize(P);
    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        rot[(a+b)%P].push_back({a, b});
        str[i] = {{a, b}, (a+b)%P};
        atpin[a] = atpin[b] = i;
    }
    pair<int,int> bsf = {0, 0};
    for(int i = 0; i < P; i++) {
        if (i % 2) {
            bsf = max(bsf, make_pair((int)rot[i].size(), i));
        }
    }
    int r = bsf.second;
    priority_queue<pair<int,int>> todo;
    for(int i = 0; i < N; i++) {
        if (str[i].second == r) {
            took[str[i].first.first] = took[str[i].first.second] = 1;
            done[i] = 1;
        }
        else todo.push({0, i});
    }
    int res = 0;
    vector<vector<int>> res2;
    while(todo.size()) {
        int i = todo.top().second;
        todo.pop();
        if (i == -1 || done[i]) continue;
        done[i] = 1;
        auto [a, b] = str[i].first;
        res++;
        if (!took[a]) {
            took[a] = 1;
            took[(r-a+P)%P] = 1;
            atpin[b] = -1;
            todo.push({1, atpin[(r-a+P)%P]});
            res2.push_back({i, b, (r-a+P)%P});
        } else {
            took[b] = 1;
            took[(r-b+P)%P] = 1;
            atpin[a] = -1;
            todo.push({1, atpin[(r-b+P)%P]});
            res2.push_back({i, a, (r-b+P)%P});
        }
    }
    cout << res << endl;
    for(int i = 0; i < res; i++) {
        cout << res2[i][0] << ' ' << res2[i][1] << ' ' << res2[i][2] << endl;
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…