Submission #6061671


Source Code Expand

Copy
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
    int n;
    cin>>n;
    int K;
    cin>>K;
    if(K>n*(n-1)/2-n+1){
        cout<<-1<<endl;
        return 0;
    }
    vector<int> e1,e2;
    rep(i,n-1){
        e1.push_back(0);
        e2.push_back(i+1);
    }
    int nokori = (n-1)*(n-2)/2-K;
    rep(i,n-1)rep(j,i){
        if(nokori==0)break;
        e1.push_back(i+1);
        e2.push_back(j+1);
        --nokori;
    }
    int dist[n][n];
    rep(i,n)rep(j,n)dist[i][j]=inf;
    rep(i,n)dist[i][i]=0;
    rep(i,e1.size()){
        dist[e1[i]][e2[i]]=1;
        dist[e2[i]][e1[i]]=1;
    }
    rep(i,n)rep(j,n)rep(k,n){
        dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]);
    }
    int cnt = 0;
    rep(i,n)rep(j,n){
        if(dist[i][j]==2)++cnt;
    }
    assert(cnt==2*K);
    cout<<e1.size()<<endl;
    rep(i,e1.size()){
        cout<<e1[i]+1<<" "<<e2[i]+1<<endl;
    }
    return 0;
}

Submission Info

Submission Time
Task E - Friendships
User tempura0224
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1413 Byte
Status AC
Exec Time 10 ms
Memory 384 KB

Judge Result

Set Name All Sample
Score / Max Score 500 / 500 0 / 0
Status
AC × 18
AC × 2
Set Name Test Cases
All sample_01, sample_02, testcase_01, testcase_02, testcase_03, testcase_04, testcase_05, testcase_06, testcase_07, testcase_08, testcase_09, testcase_10, testcase_11, testcase_12, testcase_13, testcase_14, testcase_15, testcase_16
Sample sample_01, sample_02
Case Name Status Exec Time Memory
sample_01 AC 1 ms 256 KB
sample_02 AC 1 ms 256 KB
testcase_01 AC 1 ms 256 KB
testcase_02 AC 1 ms 256 KB
testcase_03 AC 1 ms 256 KB
testcase_04 AC 10 ms 384 KB
testcase_05 AC 2 ms 256 KB
testcase_06 AC 1 ms 256 KB
testcase_07 AC 1 ms 256 KB
testcase_08 AC 1 ms 256 KB
testcase_09 AC 1 ms 256 KB
testcase_10 AC 2 ms 256 KB
testcase_11 AC 2 ms 256 KB
testcase_12 AC 1 ms 256 KB
testcase_13 AC 1 ms 256 KB
testcase_14 AC 1 ms 256 KB
testcase_15 AC 10 ms 384 KB
testcase_16 AC 2 ms 256 KB