#1038832 (C++23) No.3012 岩井星人グラフ

• 問題: No.3012 岩井星人グラフ
• ユーザー: るこーそー
• 提出日時: 2025-01-25 16:30:55
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 328 ms / 2,000 ms
• コード長: 11,197 bytes
• コンパイル時間: 6,622 ms
• コンパイル使用メモリ: 332,172 KB
• 実行使用メモリ: 5,348 KB
• 最終ジャッジ日時: 2025-01-25 23:53:17
• 合計ジャッジ時間: 12,993 ms
• ジャッジサーバーID （参考情報）: judge5 / judge6

ファイルパターン	結果
sample	AC * 2
other	AC * 23

ソースコード

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

using ll=long long;
#define rep1(i,a) for(int i=0;i<(a);i++)
#define rep2(i,a,b) for(int i=(a);i<(b);i++)
#define rep3(i,a,b,c) for(int i=(a);i<(b);i+=(c))
#define overload3(a,b,c,d,e,...) e
#define rep(...) overload3(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define chmax(x,y)((x)=max(x,y))
#define chmin(x,y)((x)=min(x,y))

template<class T> vector<T> compress(vector<T> x){
    vector<T> xs=x;
    sort(xs.begin(),xs.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end());
    rep(i,x.size()) x[i]=lower_bound(xs.begin(),xs.end(),x[i])-xs.begin();
    return x;
}
template<class T> vector<T> dijkstra(int start,vector<vector<pair<T,int>>> &graph){
    int n=graph.size();
    vector<T> dist(n,numeric_limits<T>::max());
    dist[start]=0;
    priority_queue<pair<T,int>,vector<pair<T,int>>,greater<pair<T,int>>> pq;
    pq.push({0,start});
    while(!pq.empty()){
        auto [d,v]=pq.top();pq.pop();
        if (dist[v]<d)continue;
        for (auto [nd,nv]:graph[v]){
            if (dist[nv]>d+nd){
                dist[nv]=d+nd;
                pq.push({dist[nv],nv});
            }
        }
    }
    return dist;
}
template<class T> struct BIT{
    vector<T> dat;
    BIT(int n):dat(n+1,0){}
    void add(int i,T x){
        for(++i;i<dat.size();i+=i&-i)dat[i]+=x;
    }
    T sum(int i){
        T res=0;
        for(++i;i;i-=i&-i)res+=dat[i];
        return res;
    }
    T sum(int l,int r){
        return sum(r-1)-sum(l-1);
    }
};
template<class T> struct MergeSortTree{
    int n,log,size;
    vector<vector<T>> dat,sum;
    T min_elem,max_elem;
    MergeSortTree(vector<T> a):n(a.size()){
        min_elem=*min_element(all(a));
        max_elem=*max_element(all(a));
        log=0;
        while ((1LL<<log)<n)log++;
        size=1<<log;
        dat.resize(size*2);
        sum.resize(size*2);
        for (int i=0;i<n;i++){
            dat[size+i]={a[i]};
            sum[size+i]={0,a[i]};
        }
        for (int i=size-1;i>0;i--){
            dat[i]=merge(dat[i*2],dat[i*2+1]);
            sum[i].resize(dat[i].size()+1,0);
            for (int j=1;j<sum[i].size();j++)sum[i][j]=sum[i][j-1]+dat[i][j-1];
        }
    }   
    vector<T> merge(vector<T> &l, vector<T> &r){
        vector<T> res;
        int i=0,j=0;
        while (i<l.size() && j<r.size()){
            if (l[i]<r[j])res.push_back(l[i++]);
            else res.push_back(r[j++]);
        }
        while (i<l.size())res.push_back(l[i++]);
        while (j<r.size())res.push_back(r[j++]);
        return res;
    }
    T range_sum(int l,int r,int x){
        l+=size;r+=size;
        T res=0;
        while (l<r){
            if (l&1){
                if (!dat[l].empty())res+=sum[l][upper_bound(dat[l].begin(),dat[l].end(),x)-dat[l].begin()];
                l++;
            }
            if (r&1){
                r--;
                if (!dat[r].empty())res+=sum[r][upper_bound(dat[r].begin(),dat[r].end(),x)-dat[r].begin()];
            }
            l>>=1;r>>=1;
        }
        return res;
    }
    int range_freq(int l,int r,int x){
        l+=size;r+=size;
        int res=0;
        while (l<r){
            if (l&1){
                if (!dat[l].empty())res+=upper_bound(dat[l].begin(),dat[l].end(),x)-dat[l].begin();
                l++;
            }
            if (r&1){
                r--;
                if (!dat[r].empty())res+=upper_bound(dat[r].begin(),dat[r].end(),x)-dat[r].begin();
            }
            l>>=1;r>>=1;
        }
        return res;
    }
    T range_sum(int l,int r,int x,int y){
        return range_sum(l,r,y-1)-range_sum(l,r,x-1);
    }
    int range_freq(int l,int r,int x,int y){
        return range_freq(l,r,y-1)-range_freq(l,r,x-1);
    }
    T get(int k){
        return (dat[size+k].size() ? dat[size+k][0] : T());
    }
    T kth_smallest(int l,int r,int k){
        T ng=min_elem-1,ok=max_elem+1;
        while (ok-ng>1){
            int mid=(ok+ng)/2;
            if (range_freq(l,r,mid)>k)ok=mid;
            else ng=mid;
        }
        return ok;
    }
    T kth_largest(int l,int r,int k){
        return kth_smallest(l,r,r-l-k-1);
    }
};
template<typename S> struct SplayTree{
private:
    //using S=long long;
    static S op(S a, S b) {return a + b;}
    static S e() {return 0;}
    using F = long long;
    static S mapping(F f, S x) {return f + x;}
    static F composition(F f, F g) {return f + g;}
    static F id() {return 0;}

    struct node{
        S v, prod;
        F lazy;
        int cnt, rev;
        node *l, *r;
        node(S v): v(v), prod(v), lazy(id()), cnt(1), rev(0){
            l = r = nullptr;
        }
    };

    node *root=nullptr;

    int count(node *x){return !x ? 0:x->cnt;}
    S sum(node *x){return !x ? e():x->prod;}
    node *rotate(node *x,bool right){
        node *y= right ? x->l : x->r;
        all_push(x);all_push(y);
        if (!y)return x;
        if (right){
            x->l=y->r;
            y->r=x;
        }else{
            x->r=y->l;
            y->l=x;
        }
        update(x);update(y);
        return y;
    }
    node *splay(node *x,int k){
        if (!x)return nullptr;
        all_push(x);
        if (k<count(x->l)){
            if (x->l==nullptr)return x;
            if (k<count(x->l->l)){
                x->l->l=splay(x->l->l,k);
                x=rotate(x,true);
            }else if (count(x->l->l)<k){
                x->l->r=splay(x->l->r,k-count(x->l->l)-1);
                if (x->l->r)x->l=rotate(x->l,false);
            }
            return x->l ? rotate(x,true) : update(x);
        }else if (count(x->l)<k){
            if (x->r==nullptr)return x;
            k=k-count(x->l)-1;
            if (k<count(x->r->l)){
                x->r->l=splay(x->r->l,k);
                if (x->r->l)x->r=rotate(x->r,true);
            }else if (count(x->r->l)<k){
                x->r->r=splay(x->r->r,k-count(x->r->l)-1);
                x=rotate(x,false);
            }
            return x->r ? rotate(x,false) : update(x);
        }
        return update(x);
    }
    node *merge(node *l,node *r) {
        if (!l || !r) return !l ? r : l;
        r=splay(r,0);
        r->l=l;
        return update(r);
    }
    pair<node*, node*> split(node *x, int k) {
        assert(0<=k && k<=size());
        if (!x) return {nullptr, nullptr};
        if (k==size())return {x,nullptr};
        x=splay(x, k);
        all_push(x);
        node* l=x->l;
        x->l=nullptr;
        return {l,update(x)};
    }
    void insert(node *&x,int k,S v) {
        assert(0<=k && k<=size());
        auto [l,r]=split(root,k);
        root=merge(merge(l,new node(v)),r);
    }

    void erase(node *&x,int k) {
        assert(0<=k && k<size());
        auto [left_mid,right]=split(x,k+1);
        auto [left,mid]=split(left_mid,k);
        delete mid;
        x=merge(left,right);
    }
    void erase(node *&x,int l,int r){
        assert(0<=l && r<=size() && l<=r);
        x=splay(x,l);
        auto [left,mid,right]=split3(x,l,r);
        all_push(x);
        delete mid;
        root=merge(left,right);
    }
    S get(node *&x,int k){
        assert(0<=k && k<size());
        if (!root)return e();
        x=splay(x,k);
        all_push(x);
        update(x);
        return x->v;
    }
    void set(node *&x,int k,S v){
        assert(0<=k && k<size());
        x=splay(x,k);
        x->v=v;
    }
    S prod(node *&x,int l,int r) {
        assert(0<=l && r<=size() && l<=r);
        x=splay(x,l);
        auto [left,mid,right]=split3(x,l,r);
        all_push(mid);
        S res=sum(update(mid));
        x=merge(merge(left,mid),right);
        return res;
    }
    void apply(node *&x,int l,int r,F f){
        assert(0<=l && r<=size() && l<=r);
        x=splay(x,l);
        auto [left,mid,right]=split3(x,l,r);
        if (mid)mid->lazy=composition(f,mid->lazy);
        x=merge(merge(left,mid),right);
    }
    void reverse(node *&x,int l,int r){
        assert(0<=l && r<=size() && l<=r);
        auto [left,mid,right]=split3(x,l,r);
        if (mid)mid->rev=1;
        x=merge(merge(left,mid),right);
    }
    void push(node *x){
        if (!x)return;
        if (x->lazy!=id()){
            x->v=mapping(x->lazy,x->v);
            x->prod=mapping(x->lazy,x->prod);
            if (x->l)x->l->lazy=composition(x->lazy,x->l->lazy);
            if (x->r)x->r->lazy=composition(x->lazy,x->r->lazy);
            x->lazy=id();
        }
        if (x->rev){
            swap(x->l,x->r);
            if (x->l)x->l->rev^=1;
            if (x->r)x->r->rev^=1;
            x->rev=0;
        }
    }
    void all_push(node *x){
        push(x);
        if (x)push(x->l),push(x->r);
    }
    node *update(node *x){
        if (!x)return x;
        x->cnt=count(x->l)+count(x->r)+1;
        x->prod=op(op(sum(x->l),x->v),sum(x->r));
        return x;
    }
    tuple<node*, node*, node*> split3(node *x,int l,int r){
        auto [left_mid,right]=split(x,r);
        auto [left,mid]=split(left_mid,l);
        return {left,mid,right};
    }

    int bisect_left(node *x,S v){
        all_push(x);
        if (!x)return 0;
        if (v<=x->v)return bisect_left(x->l,v);
        return count(x->l)+1+bisect_left(x->r,v);
    }
    int bisect_right(node *x,S v){
        all_push(x);
        if (!x)return 0;
        if (v<x->v)return bisect_right(x->l,v);
        return count(x->l)+1+bisect_right(x->r,v);
    }
    node *make_tree(vector<S> &v,int l,int r){
        if (r-l==0)return nullptr;
        int m=l+(r-l)/2;
        node *left=make_tree(v,l,m), *right=make_tree(v,m+1,r);
        node *x=new node(v[m]);
        x->l=left;x->r=right;
        return update(x);
    }
public:
    SplayTree(){}
    SplayTree(vector<S> v){ root=make_tree(v, 0, v.size()); }
    int size(){return (!root ? 0 : root->cnt);}
    void insert_at(int k, S v){ insert(root, k, v); }
    void insert(S v){ insert(bisect_left(v), v);}
    void erase_at(int k){ erase(root, k); }
    void erase(S v){ erase_at(bisect_left(v)); }
    int count(S v){ return bisect_right(v)-bisect_left(v); }
    S get(int k){ return get(root, k); }
    void set(int k, S v){ set(root, k, v); }
    S prod(int l, int r){ return prod(root, l, r); }
    void apply(int l, int r, F f){ apply(root, l, r, f); }
    int bisect_left(S v){ root=splay(root, size()); return bisect_left(root, v); }
    int bisect_right(S v){ root=splay(root, size()); return bisect_right(root, v); }
    S lower_bound(S v){ return get(bisect_left(v)); }
    S upper_bound(S v){ return get(bisect_right(v)); }
    void reverse(int l, int r){ reverse(root, l, r); }
};

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int x,y;
    cin >> x >> y;
    vector<pair<int,int>> edges;
    rep(i,x){
        edges.emplace_back(i,(i+1)%x);
    }
    rep(i,x){
        int u=i;
        rep(j,y-2){
            int v=edges.size();
            edges.emplace_back(u,v);
            u=v;
        }
        edges.emplace_back(u,edges.size());
    }

    cout << edges.size() << " " << edges.size() << endl;
    for (auto &[u,v]:edges){
        cout << u+1 << " " << v+1 << endl;
    }
}