fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #pragma GCC optimize("inline")
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. inline int my_getchar_unlocked(){
  7.   static char buf[1048576];
  8.   static int s = 1048576;
  9.   static int e = 1048576;
  10.   if(s == e && e == 1048576){
  11.     e = fread_unlocked(buf, 1, 1048576, stdin);
  12.     s = 0;
  13.   }
  14.   if(s == e){
  15.     return EOF;
  16.   }
  17.   return buf[s++];
  18. }
  19. inline void rd(int &x){
  20.   int k;
  21.   int m=0;
  22.   x=0;
  23.   for(;;){
  24.     k = my_getchar_unlocked();
  25.     if(k=='-'){
  26.       m=1;
  27.       break;
  28.     }
  29.     if('0'<=k&&k<='9'){
  30.       x=k-'0';
  31.       break;
  32.     }
  33.   }
  34.   for(;;){
  35.     k = my_getchar_unlocked();
  36.     if(k<'0'||k>'9'){
  37.       break;
  38.     }
  39.     x=x*10+k-'0';
  40.   }
  41.   if(m){
  42.     x=-x;
  43.   }
  44. }
  45. struct MY_WRITER{
  46.   char buf[1048576];
  47.   int s;
  48.   int e;
  49.   MY_WRITER(){
  50.     s = 0;
  51.     e = 1048576;
  52.   }
  53.   ~MY_WRITER(){
  54.     if(s){
  55.       fwrite_unlocked(buf, 1, s, stdout);
  56.     }
  57.   }
  58. }
  59. ;
  60. MY_WRITER MY_WRITER_VAR;
  61. void my_putchar_unlocked(int a){
  62.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  63.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  64.     MY_WRITER_VAR.s = 0;
  65.   }
  66.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  67. }
  68. inline void wt_L(char a){
  69.   my_putchar_unlocked(a);
  70. }
  71. inline void wt_L(int x){
  72.   int s=0;
  73.   int m=0;
  74.   char f[10];
  75.   if(x<0){
  76.     m=1;
  77.     x=-x;
  78.   }
  79.   while(x){
  80.     f[s++]=x%10;
  81.     x/=10;
  82.   }
  83.   if(!s){
  84.     f[s++]=0;
  85.   }
  86.   if(m){
  87.     my_putchar_unlocked('-');
  88.   }
  89.   while(s--){
  90.     my_putchar_unlocked(f[s]+'0');
  91.   }
  92. }
  93. inline void wt_L(const char c[]){
  94.   int i=0;
  95.   for(i=0;c[i]!='\0';i++){
  96.     my_putchar_unlocked(c[i]);
  97.   }
  98. }
  99. template<class S> inline void arrInsert(const int k, int &sz, S a[], const S aval){
  100.   int i;
  101.   sz++;
  102.   for(i=sz-1;i>k;i--){
  103.     a[i] = a[i-1];
  104.   }
  105.   a[k] = aval;
  106. }
  107. template<class S, class T> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){
  108.   int i;
  109.   sz++;
  110.   for(i=sz-1;i>k;i--){
  111.     a[i] = a[i-1];
  112.   }
  113.   for(i=sz-1;i>k;i--){
  114.     b[i] = b[i-1];
  115.   }
  116.   a[k] = aval;
  117.   b[k] = bval;
  118. }
  119. template<class S, class T, class U> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){
  120.   int i;
  121.   sz++;
  122.   for(i=sz-1;i>k;i--){
  123.     a[i] = a[i-1];
  124.   }
  125.   for(i=sz-1;i>k;i--){
  126.     b[i] = b[i-1];
  127.   }
  128.   for(i=sz-1;i>k;i--){
  129.     c[i] = c[i-1];
  130.   }
  131.   a[k] = aval;
  132.   b[k] = bval;
  133.   c[k] = cval;
  134. }
  135. template<class S, class T, class U, class V> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval, V d[], const V dval){
  136.   int i;
  137.   sz++;
  138.   for(i=sz-1;i>k;i--){
  139.     a[i] = a[i-1];
  140.   }
  141.   for(i=sz-1;i>k;i--){
  142.     b[i] = b[i-1];
  143.   }
  144.   for(i=sz-1;i>k;i--){
  145.     c[i] = c[i-1];
  146.   }
  147.   for(i=sz-1;i>k;i--){
  148.     d[i] = d[i-1];
  149.   }
  150.   a[k] = aval;
  151.   b[k] = bval;
  152.   c[k] = cval;
  153.   d[k] = dval;
  154. }
  155. int main(){
  156.   int i;
  157.   int K;
  158.   rd(K);
  159.   int N;
  160.   int mat[20][20] = {};
  161.   int x;
  162.   int y;
  163.   int nx;
  164.   int M;
  165.   int A[400];
  166.   int B[400];
  167.   if(K==1){
  168.     wt_L("2 1\n1 2");
  169.     wt_L('\n');
  170.     return 0;
  171.   }
  172.   if(K==2){
  173.     wt_L("4 4\n1 2\n1 3\n2 3\n3 4");
  174.     wt_L('\n');
  175.     return 0;
  176.   }
  177.   if(K <= 20){
  178.     int i;
  179.     wt_L(K);
  180.     wt_L(' ');
  181.     wt_L(K);
  182.     wt_L('\n');
  183.     for(i=(0);i<(K);i++){
  184.       wt_L(i+1);
  185.       wt_L(' ');
  186.       wt_L((i+1)%K+1);
  187.       wt_L('\n');
  188.     }
  189.     return 0;
  190.   }
  191.   for(x=(0);x<(20);x++){
  192.     if((x*x + x - 2)/2 + x - 1 > K){
  193.       break;
  194.     }
  195.   }
  196.   x--;
  197.   y = K - ((x*x + x - 2)/2 + x - 1) + 2;
  198.   for(i=(0);i<(x);i++){
  199.     int j;
  200.     for(j=(i+1);j<(x);j++){
  201.       if(i!=j){
  202.         mat[i][j] = 1;
  203.       }
  204.     }
  205.   }
  206.   mat[x-2][x-1] = 0;
  207.   mat[x-1][x] = 1;
  208.   for(i=(0);i<(y);i++){
  209.     nx = x + i + 1;
  210.     if(i == y - 1){
  211.       nx = x-2;
  212.     }
  213.     mat[x+i][nx] = mat[nx][x+i] = 1;
  214.   }
  215.   auto KrdatlYV = ((x + y));
  216.   auto ao_dF3pO = (( 0));
  217.   N=KrdatlYV;
  218.   M=ao_dF3pO;
  219.   for(i=(0);i<(N);i++){
  220.     int j;
  221.     for(j=(i+1);j<(N);j++){
  222.       if(mat[i][j]){
  223.         arrInsert(M,M,A,i,B,j);
  224.       }
  225.     }
  226.   }
  227.   wt_L(N);
  228.   wt_L(' ');
  229.   wt_L(M);
  230.   wt_L('\n');
  231.   for(i=(0);i<(M);i++){
  232.     wt_L(A[i]+1);
  233.     wt_L(' ');
  234.     wt_L(B[i]+1);
  235.     wt_L('\n');
  236.   }
  237.   return 0;
  238. }
  239. // cLay version 20210917-1
  240.  
  241. // --- original code ---
  242. // int @K;
  243. // int N, mat[20][20] = {}, x, y, nx;
  244. // int M, A[400], B[400];
  245. // 
  246. // if(K==1) wt("2 1\n1 2"), return 0;
  247. // if(K==2) wt("4 4\n1 2\n1 3\n2 3\n3 4"), return 0;
  248. // if(K <= 20){
  249. //   wt(K, K);
  250. //   rep(i,K) wt(i+1, (i+1)%K+1);
  251. //   return 0;
  252. // }
  253. // 
  254. // rep(x,20) if((x*x + x - 2)/2 + x - 1 > K) break;
  255. // x--;
  256. // y = K - ((x*x + x - 2)/2 + x - 1) + 2;
  257. // 
  258. // rep(i,x) rep(j,i+1,x) if(i!=j) mat[i][j] = 1;
  259. // mat[x-2][x-1] = 0;
  260. // mat[x-1][x] = 1;
  261. // rep(i,y){
  262. //   nx = x + i + 1;
  263. //   if(i == y - 1) nx = x-2;
  264. //   mat[x+i][nx] = mat[nx][x+i] = 1;
  265. // }
  266. // 
  267. // (N, M) = (x + y, 0);
  268. // rep(i,N) rep(j,i+1,N) if(mat[i][j]) arrInsert(M,M,A,i,B,j);
  269. // wt(N,M);
  270. // rep(i,M) wt(A[i]+1,B[i]+1);
  271.  
Time limit exceeded #stdin #stdout 5s 5424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FO2AkX
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!