結果
問題 | No.1519 Diversity |
ユーザー |
![]() |
提出日時 | 2021-05-28 21:20:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 14 ms / 2,000 ms |
コード長 | 848 bytes |
コンパイル時間 | 3,996 ms |
コンパイル使用メモリ | 255,392 KB |
最終ジャッジ日時 | 2025-01-21 19:38:32 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 15 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint1000000007;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000001int main(){int N;cin>>N;priority_queue<pair<int,int>> Q;Q.emplace(1,0);Q.emplace(1,1);vector<int> a(1,0),b(1,1);vector<int> d(N,0);d[0] = 1;d[1] = 1;for(int i=2;i<N;i++){vector<int> inds;while(true){pair<int,int> p = Q.top();Q.pop();if(Q.size()==0 || d[i]+1>Q.top().first+1){Q.push(p);break;}inds.push_back(p.second);d[i]++;}rep(j,inds.size()){a.push_back(i);b.push_back(inds[j]);d[inds[j]]++;Q.emplace(d[inds[j]],inds[j]);}Q.emplace(d[i],i);}cout<<a.size()<<endl;rep(i,a.size()){printf("%d %d\n",a[i]+1,b[i]+1);}return 0;}