#882511 (C++14) No.2353 Guardian Dogs in Spring

• 問題: No.2353 Guardian Dogs in Spring
• ユーザー: nocturnal_1202
• 提出日時: 2023-06-17 18:17:42
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 16 ms / 2,000 ms
• コード長: 13,892 bytes
• コンパイル時間: 1,989 ms
• コンパイル使用メモリ: 158,512 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-06-25 08:26:38
• 合計ジャッジ時間: 7,519 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	AC	2 ms; 6,944 KB
testcase_02	AC	2 ms; 6,944 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	2 ms; 6,940 KB
testcase_05	AC	13 ms; 6,940 KB
testcase_06	AC	13 ms; 6,940 KB
testcase_07	AC	14 ms; 6,944 KB
testcase_08	AC	14 ms; 6,948 KB
testcase_09	AC	14 ms; 6,940 KB
testcase_10	AC	14 ms; 6,940 KB
testcase_11	AC	14 ms; 6,940 KB
testcase_12	AC	15 ms; 6,940 KB
testcase_13	AC	14 ms; 6,940 KB
testcase_14	AC	2 ms; 6,940 KB
testcase_15	AC	16 ms; 6,940 KB
testcase_16	AC	15 ms; 6,940 KB
testcase_17	AC	16 ms; 6,944 KB
testcase_18	AC	15 ms; 6,940 KB
testcase_19	AC	16 ms; 6,940 KB
testcase_20	AC	2 ms; 6,940 KB
testcase_21	AC	4 ms; 6,948 KB
testcase_22	AC	8 ms; 6,940 KB
testcase_23	AC	14 ms; 6,940 KB
testcase_24	AC	4 ms; 6,940 KB
testcase_25	AC	3 ms; 6,940 KB
testcase_26	AC	3 ms; 6,940 KB
testcase_27	AC	3 ms; 6,944 KB
testcase_28	AC	5 ms; 6,944 KB
testcase_29	AC	10 ms; 6,940 KB
testcase_30	AC	8 ms; 6,944 KB
testcase_31	AC	9 ms; 6,940 KB
testcase_32	AC	14 ms; 6,944 KB
testcase_33	AC	14 ms; 6,944 KB
testcase_34	AC	14 ms; 6,944 KB
testcase_35	AC	14 ms; 6,940 KB
testcase_36	AC	4 ms; 6,944 KB
testcase_37	AC	4 ms; 6,940 KB
testcase_38	AC	6 ms; 6,944 KB
testcase_39	AC	7 ms; 6,940 KB
testcase_40	AC	9 ms; 6,944 KB
testcase_41	AC	10 ms; 6,944 KB

ソースコード

#include <algorithm>
#include <bitset>
#include <complex>
#include <cassert>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <math.h>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include<regex>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,x) for(ll i=0;i<(ll)(x);i++)
#define rrep(i,x) for(ll i=1;i<=(ll)(x);i++)
#define all(v) v.begin(),v.end()
#define veci vector<int>
#define vecl vector<ll>
typedef pair<int, int> pii;
ll INF = 1e17;
ll mod998 = 998244353;
ll mod109 = 1e9 + 7;
//vector<vector<int>> a(n,vector<int>(n));

struct mint {
    const long long mod = mod998;
    long long x;
    mint(long long x_ = 0) : x((x_% mod + mod) % mod) {}

    mint& operator+=(const mint& other) {
        x += other.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& other) {
        x -= other.x;
        if (x < 0) x += mod;
        return *this;
    }
    mint& operator*=(const mint& other) {
        x *= other.x;
        x %= mod;
        return *this;
    }

    mint& operator+=(const long long n) {
        return *this += mint(n);
    }
    mint& operator-=(const long long n) {
        return *this -= mint(n);
    }
    mint& operator*=(const long long n) {
        return *this *= mint(n);
    }

    mint& operator=(const mint& other) {
        x = other.x;
        return *this;
    }
    mint& operator=(const long long n) {
        x = n % mod;
        return *this;
    }

    bool operator==(const mint& other) const {
        return x == other.x;
    }
    bool operator!=(const mint& other) const {
        return x != other.x;
    }

    mint operator-() const {
        mint res(mod - x);
        return res;
    }

    mint operator+(const mint& other) const {
        mint res(x);
        return res += other;
    }
    mint operator-(const mint& other) const {
        mint res(x);
        return res -= other;
    }
    mint operator*(const mint& other) const {
        mint res(x);
        return res *= other;
    }

    mint operator+(const long long n) const {
        mint res(x);
        mint other(n);
        return res += other;
    }
    mint operator-(const long long n) const {
        mint res(x);
        mint other(n);
        return res -= other;
    }
    mint operator*(const long long n) const {
        mint res(x);
        mint other(n);
        return res *= other;
    }

    mint pow(long long n) const {
        if (n == 0) return mint(1);
        mint res = pow(n / 2);
        res *= res;
        if (n % 2) res *= *this;
        return res;
    }
    mint inv() const {
        return pow(mod - 2);
    }
    mint& operator/=(const mint& other) {
        *this *= other.inv();
        return *this;
    }
    mint operator/(const mint& other) const {
        mint res(x);
        return res /= other;
    }
};

struct combination {
    vector<mint> fact, ifact;
    combination(int m) :fact(m + 1), ifact(m + 1) {
        fact[0] = 1;
        for (int i = 1; i <= m; i++) fact[i] = fact[i - 1] * mint(i);
        ifact[m] = fact[m].inv();
        for (int i = m; i >= 1; i--) ifact[i - 1] = ifact[i] * mint(i);
    }
    mint operator()(int n, int k) {//for n<=m, calc nck
        if (k < 0 || k > n) return mint(0);
        return fact[n] * ifact[k] * ifact[n - k];
    }
};

/* UnionFind：素集合系管理の構造体(union by rank)
    isSame(x, y): x と y が同じ集合にいるか。 計算量はならし O(α(n))
    unite(x, y): x と y を同じ集合にする。計算量はならし O(α(n))
*/
struct UnionFind {  // The range of node number is u 0 v n-1
    vector<int> rank, parents;
    UnionFind() {}
    UnionFind(int n) {  // make n trees.
        rank.resize(n, 0);
        parents.resize(n, 0);
        for (int i = 0; i < n; i++) {
            makeTree(i);
        }
    }
    void makeTree(int x) {
        parents[x] = x;  // the parent of x is x
        rank[x] = 0;
    }
    bool isSame(int x, int y) { return findRoot(x) == findRoot(y); }
    void unite(int x, int y) {
        x = findRoot(x);
        y = findRoot(y);
        if (rank[x] > rank[y]) {
            parents[y] = x;
        }
        else {
            parents[x] = y;
            if (rank[x] == rank[y]) {
                rank[y]++;
            }
        }
    }
    int findRoot(int x) {
        if (x != parents[x]) parents[x] = findRoot(parents[x]);
        return parents[x];
    }

};
struct dsu {
public:
    dsu() : _n(0) {}
    explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

//DFSの基本形
/*vector<bool> seen;
void dfs(const vector<vector<int>>& G, int v) {
    seen[v] = true; // v を訪問済にする

    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) {
        if (seen[next_v]) continue; // next_v が探索済だったらスルー
        dfs(G, next_v); // 再帰的に探索
    }
}*/

//dijkstra法
struct Edge1 {
    long long to;
    long long cost;
};
using GraphE1 = vector<vector<Edge1>>;
using P = pair<long, int>;

/* dijkstra(G,s,dis)
    入力：グラフ G, 開始点 s, 距離を格納する dis
    計算量：O(|E|log|V|)
    副作用：dis が書き換えられる
*/
void dijkstra(const GraphE1& G, int s, vector<long long>& dis) {
    priority_queue<P, vector<P>, greater<P>> pq;  // 「仮の最短距離, 頂点」が小さい順に並ぶ
    dis[s] = 0;
    pq.emplace(dis[s], s);
    while (!pq.empty()) {
        P p = pq.top();
        pq.pop();
        int v = p.second;
        if (dis[v] < p.first) {  // 最短距離で無ければ無視
            continue;
        }
        for (auto& e : G[v]) {
            // 最短距離候補なら priority_queue に追加
            if (dis[e.to] > dis[v] + e.cost) {
                // 最短距離候補なら priority_queue に追加
                dis[e.to] = dis[v] + e.cost;
                pq.emplace(dis[e.to], e.to);
            }
        }
    }
}

/*
Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // BFS のためのデータ構造
    vector<int> dist(N, -1); // 全頂点を「未訪問」に初期化
    queue<int> que;

    // 初期条件 (頂点 0 を初期ノードとする)
    dist[0] = 0;
    que.push(0); // 0 を橙色頂点にする

    // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.front(); // キューから先頭頂点を取り出す
        que.pop();

        // v から辿れる頂点をすべて調べる
        for (int nv : G[v]) {
            if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない

            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            dist[nv] = dist[v] + 1;
            que.push(nv);
        }
    }
*/
void yesno(bool non) {
    if (non)cout << "Yes" << endl;
    else cout << "No" << endl;
}

void noyes(bool non) {
    if (non)cout << "No" << endl;
    else cout << "Yes" << endl;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

ll gcd(ll a, ll b) {
    if (a % b == 0) {
        return b;
    }
    else {
        return gcd(b, a % b);
    }
}

ll lcm(ll a, ll b) {
    return a * b / gcd(a, b);
}

//素数判定
bool is_prime(const unsigned n) {
    switch (n) {
    case 0: // fall-through
    case 1: return false;
    } // n > 1 が保証された

    // n より小さい数で n を割って余りを調べる
    // 素数ならば自分より小さい数(1以外)では割り切れない
    for (unsigned i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }

    return true;
}


//mod mでaの逆元を計算.
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}


//素因数分解(O(√N)).
vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({ a, ex });
    }

    // 最後に残った数について
    if (N != 1) res.push_back({ N, 1 });
    return res;
}
//aをbで何回割れるか(O(logN)).
ll factorcnt(ll a, ll b) {
    ll cnt = 0;
    while (a % b == 0) {
        a = a / b;
        cnt++;
    }
    return cnt;

}

const int MOD = mod998;
vector<long long> fact, fact_inv, inv;
/*  init_nCk :二項係数のための前処理
    計算量:O(n)
*/
void init_nCk(int SIZE) {
    fact.resize(SIZE + 5);
    fact_inv.resize(SIZE + 5);
    inv.resize(SIZE + 5);
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE + 5; i++) {
        fact[i] = fact[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
    }
}
/*  nCk :MODでの二項係数を求める(前処理 int_nCk が必要)
    計算量:O(1)
*/
long long nCk(int n, int k) {
    assert(!(n < k));
    assert(!(n < 0 || k < 0));
    return fact[n] * (fact_inv[k] * fact_inv[n - k] % MOD) % MOD;
}



struct Edge {
    long long u;
    long long v;
    long long cost;
};
bool comp_e(const Edge& e1, const Edge& e2) { return e1.cost < e2.cost; } // 辺を直接比較するための関数
/* Kruskal :クラスカル法で minimum spanning tree を求める構造体
    入力: 辺のvector, 頂点数V
    最小全域木の重みの総和: sum
    計算量: O(|E|log|V|)
*/
struct Kruskal {
    UnionFind uft;
    long long sum;  // 最小全域木の重みの総和
    vector<Edge> edges;
    int V;
    Kruskal(const vector<Edge>& edges_, int V_) : edges(edges_), V(V_) { init(); }
    void init() {
        sort(edges.begin(), edges.end(), comp_e); // 辺の重みでソート
        uft = UnionFind(V);
        sum = 0;
        for (auto e : edges) {
            if (!uft.isSame(e.u, e.v)) { // 閉路にならなければ加える
                uft.unite(e.u, e.v);
                sum += e.cost;
            }
        }
    }
};
//DFSの基本形
/*vector<bool> seen;
void dfs(const vector<vector<int>>& G, int v) {
    seen[v] = true; // v を訪問済にする

    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) {
        if (seen[next_v]) continue; // next_v が探索済だったらスルー
        dfs(G, next_v); // 再帰的に探索
    }
}*/

//繰り返し二乗法
long long pow(long long a, long long n, long long m) {
    long long ret = 1;
    for (; n > 0; n >>= 1, a = a * a % m) {
        if (n % 2 == 1) {
            ret = ret * a % m;

        }
    }
    return ret;
}

//ios::sync_with_stdio(false);
//std::cin.tie(nullptr);



int main() {

    int n;
    cin >> n;
    vector<pii> p;
    map<pii, int> mp;
    for (int i = 0; i < n; i++) {
        int x, y; cin >> x >> y;
        x--, y--;
        p.push_back({ x,y });
        mp[p[i]] = i + 1;
    }
    sort(all(p));

    queue<int > que;
    vector<pii> ans;
    for (int i = 0; i < n; i++) {
        que.push(mp[p[i]]);
        if (que.size() == 2) {
            int x = que.front(); que.pop();
            int y = que.front(); que.pop();
            ans.push_back({ x, y });
        }
    }
    cout << ans.size() << endl;
    for (pii i : ans) {
        cout << i.first << " " << i.second << endl;
    }

}