fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. mt19937 gen;
  5.  
  6. int gen_inrange(int a, int b){
  7.     return gen() % (b-a+1)+a;
  8. }
  9.  
  10. int main(){
  11.     ios_base::sync_with_stdio(0);
  12.     cin.tie(0);
  13.  
  14.     int t;
  15.     int c;
  16.     cin>>t>>c;
  17.  
  18.     if(t==1){
  19.         for(int i=0;i<c;i++){
  20.             int n;
  21.             cin>>n;
  22.             cout<<n<<" "<<n-1<<"\n";
  23.  
  24.             for(int i=2;i<=n;i++){
  25.                 if(gen_inrange(0,1)==1){
  26.                     cout<<gen_inrange(1,i-1)<<" "<<i<<"\n";
  27.                 }else{
  28.                     cout<<i<<" "<<gen_inrange(1,i-1)<<"\n";
  29.                 }
  30.  
  31.             }
  32.             cout<<"\n";
  33.  
  34.         }
  35.     }
  36.     if(t==2){
  37.         for(int i=0;i<c;i++){
  38.             int n;
  39.             cin>>n;
  40.             cout<<n<<" "<<n-1<<"\n";
  41.             vector<int> v (n);
  42.             for(int i=0;i<n;i++){
  43.                 v[i]=i+1;
  44.             }
  45.  
  46.             shuffle(v.begin(),v.end(),gen);
  47.  
  48.             for(int i=0;i<n-1;i++){
  49.                 cout<<v[i]<<" "<<v[i+1]<<"\n";
  50.  
  51.             }
  52.             cout<<"\n";
  53.  
  54.         }
  55.     }
  56.     if(t==3){
  57.         for(int i=0;i<c;i++){
  58.             int n;
  59.             cin>>n;
  60.             cout<<n<<" "<<n-1<<"\n";
  61.             vector<int> v (n);
  62.             for(int i=0;i<n;i++){
  63.                 v[i]=i+1;
  64.             }
  65.             set<pair<int,int>> s;
  66.  
  67.             shuffle(v.begin(),v.end(),gen);
  68.  
  69.             for(int i=1;i<n;i++){
  70.                 if(gen_inrange(0,1)==1){
  71.                     cout<<v[0]<<" "<<v[i]<<"\n";
  72.                 }else{
  73.                     cout<<v[i]<<" "<<v[0]<<"\n";
  74.                 }
  75.  
  76.             }
  77.             cout<<"\n";
  78.  
  79.         }
  80.     }
  81.  
  82.  
  83.     if((t==4)||(t==7)){
  84.         for(int i=0;i<c;i++){
  85.             int n,m;
  86.             cin>>n>>m;
  87.             cout<<n<<" "<<m<<"\n";
  88.  
  89.             set<pair<int,int>> krawedzie;
  90.  
  91.             while(krawedzie.size()<m){
  92.                 int a,b;
  93.                 a=gen_inrange(1,n);
  94.                 b=gen_inrange(1,n);
  95.  
  96.                 if(a==b) continue;
  97.                 if(a>b) swap(a,b);
  98.                 krawedzie.insert({a,b});
  99.             }
  100.  
  101.             for(auto [a,b]:krawedzie){
  102.                 if(gen_inrange(0,1)==1){
  103.                     cout<<a<<" "<<b<<"\n";
  104.                 }else{
  105.                     cout<<b<<" "<<a<<"\n";
  106.                 }
  107.             }
  108.         }
  109.     }
  110.     if(t==5){
  111.         for(int i=0;i<c;i++){
  112.             int n;
  113.             cin>>n;
  114.             int m=n*(n-1)/2;
  115.             cout<<n<<" "<<m<<"\n";
  116.             vector<pair<int,int>> kra(m);
  117.             int s=0;
  118.             for(int i=1;i<n;i++){
  119.                 for(int j=i+1;j<n+1;j++){
  120.                     if(gen_inrange(0,1)==1){
  121.                         kra[s]={i,j};
  122.                         s++;
  123.                     }else{
  124.                         kra[s]={j,i};
  125.                         s++;
  126.                     }
  127.                 }
  128.  
  129.             }
  130.             shuffle(kra.begin(),kra.end(),gen);
  131.             for(int i=0;i<m;i++){
  132.                 cout<<kra[i].first<<" "<<kra[i].second<<"\n";
  133.             }
  134.             cout<<"\n";
  135.         }
  136.     }
  137.     if(t==6){
  138.                 for(int i=0;i<c;i++){
  139.             int n,m;
  140.             cin>>n>>m;
  141.             cout<<n<<" "<<m<<"\n";
  142.  
  143.             set<pair<int,int>> krawedzie;
  144.             for(int i=1;i<=n-1;i++){
  145.                 for(int j=i+1;j<=n;j++){
  146.                     krawedzie.insert({i,j});
  147.                 }
  148.             }
  149.  
  150.             while(krawedzie.size()>m){
  151.                 int a,b;
  152.                 a=gen_inrange(1,n);
  153.                 b=gen_inrange(1,n);
  154.  
  155.                 if(a==b) continue;
  156.                 if(a>b) swap(a,b);
  157.                 krawedzie.erase({a,b});
  158.             }
  159.  
  160.             for(auto [a,b]:krawedzie){
  161.                 if(gen_inrange(0,1)==1){
  162.                     cout<<a<<" "<<b<<"\n";
  163.                 }else{
  164.                     cout<<b<<" "<<a<<"\n";
  165.                 }
  166.             }
  167.         }
  168.     }
  169.     if(t==8){
  170.         for(int i=0;i<c;i++){
  171.             int n,m;
  172.             cin>>n>>m;
  173.             cout<<n<<" "<<m<<"\n";
  174.             vector<int> v (n);
  175.             for(int i=0;i<n;i++){
  176.                 v[i]=i+1;
  177.             }
  178.             set<pair<int,int>> s;
  179.  
  180.             shuffle(v.begin(),v.end(),gen);
  181.  
  182.             for(int i=0;i<m;i++){
  183.                 bool x=false;
  184.  
  185.                 while(x==false){
  186.                     int a=gen_inrange(0,n-1);
  187.                     int b=gen_inrange(0,n-1);
  188.                     if(a>b) swap(a,b);
  189.                     if((s.count({a,b})==0)&&(a!=b)){
  190.                         x=true;
  191.                         s.insert({a,b});
  192.                         cout<<v[a]<<" "<<v[b]<<"\n";
  193.                     }
  194.                 }
  195.  
  196.             }
  197.             cout<<"\n";
  198.  
  199.         }
  200.     }
  201.     if(t==9){
  202.         for(int q=0; q<c;q++){
  203.             int n;
  204.             cin>>n;
  205.             cout<<n<<" "<<n-1<<"\n";
  206.             if(n==1){
  207.                 cout<<"\n";
  208.                 continue;
  209.             }
  210.             vector<int> v (n+1);
  211.             for(int i=1;i<n+1;i++){
  212.                 v[i]=i;
  213.             }
  214.  
  215.             shuffle(v.begin()+1,v.end(),gen);
  216.  
  217.             int a=1;
  218.             while(2*a-1<n){
  219.                 a*=2;
  220.             }//2a geq n
  221.  
  222.             vector<bool> los (a);
  223.             for(int i=0; i<n-a+1;i++){
  224.                 los[i]=1;
  225.             }
  226.             shuffle(los.begin(),los.end(),gen);
  227.  
  228.             vector<int> tree (2*a);
  229.             for(int i=1; i<=a-1;i++){
  230.                 tree[i]=i;
  231.             }
  232.             int k=a;
  233.             for(int i=a;i<2*a;i++){
  234.                 if(los[i-a]){
  235.                     tree[i]=k;
  236.                     k++;
  237.                 }
  238.             }
  239.  
  240.  
  241.             //            for(int i=2;i<a;i++){
  242.             //                    int e=i/2;
  243.             //                    cout<<v[e]<<" "<<v[i]<<"\n";
  244.             //
  245.             //            }
  246.             //            for(int i=a;i<2*a;i++){
  247.             //                if(los[i-a]){
  248.             //                    int e=i/2;
  249.             //                    cout<<v[e]<<" "<<v[tree[i]]<<"\n";
  250.             //
  251.             //                }
  252.             //            }
  253.             //
  254.             //
  255.             //
  256.             //            cout<<"\n\n\n";
  257.             for(int i=2;i<n+1;i++){
  258.                 int e=i/2;
  259.                     if(gen_inrange(0,1)==1){
  260.                         cout<<e<<" "<<i<<"\n";
  261.                     }else{
  262.                         cout<<i<<" "<<e<<"\n";
  263.                     }
  264.  
  265.  
  266.             }
  267. //            for(int i=a;i<2*a;i++){
  268. //                if(los[i-a]){
  269. //                    int e=i/2;
  270. //                    if(gen_inrange(0,1)==1){
  271. //                        cout<<e<<" "<<tree[i]<<"\n";
  272. //                    }else{
  273. //                        cout<<tree[i]<<" "<<e<<"\n";
  274. //                    }
  275. //
  276. //                }
  277. //            }
  278. //            cout<<"\n";
  279.  
  280.         }
  281.     }
  282.     if(t==10){
  283.         for(int i=0;i<c;i++){
  284.             int n,m,k;
  285.             cin>>n>>m>>k;
  286.             vector<int> rep (n);//////indeks reprezentanta (0___k-1)
  287.             vector<vector<int>> indeksy (k);
  288.             vector<set<pair<int,int>>> krawedzie (k);
  289.             int liczkraw=0;
  290.             for(int i=0;i<2*k;i++){
  291.                 rep[i]=i%k;
  292.                 indeksy[rep[i]].push_back(i);
  293.                 if(i>=k){
  294.                     krawedzie[rep[i]].insert({i-k,i});
  295.                     liczkraw++;
  296.                 }
  297.             }
  298.             for(int i=2*k; i<n; i++){
  299.                 rep[i]=gen_inrange(0,k-1);
  300.                 int indpol = gen_inrange(0,indeksy[rep[i]].size()-1);
  301.                 indeksy[rep[i]].push_back(i);
  302.                 krawedzie[rep[i]].insert({indeksy[rep[i]][indpol],i});
  303.                 liczkraw++;
  304.             }
  305.  
  306.             while(liczkraw<m){
  307.                 int spojna=gen_inrange(0,k-1);
  308.                 int maks =indeksy[spojna].size()-1;
  309.                 int a=gen_inrange(0,maks);
  310.                 int b=gen_inrange(0,maks);
  311.                 if(a==b) continue;
  312.                 a = indeksy[spojna][a]; b = indeksy[spojna][b];
  313.                 if(b<a) swap(a,b);
  314.                 int temp = krawedzie[spojna].size();
  315.                 krawedzie[spojna].insert({a,b});
  316.                 if(krawedzie[spojna].size()>temp){
  317.                     liczkraw++;
  318.                 }
  319.             }
  320.             cout<<n<<" "<<m <<" "<<k<<"\n";
  321.             vector<int> v (n);
  322.             for(int i=0;i<n;i++){
  323.                 v[i]=i+1;
  324.             }
  325.             shuffle(v.begin(),v.end(),gen);
  326.  
  327.             for(int i=0; i<k; i++){
  328.                 for(auto [x,y]:krawedzie[i]){
  329.                     if(gen_inrange(0,1)==1){
  330.                         cout<<v[x]<<" "<<v[y]<<"\n";
  331.                     }else{
  332.                         cout<<v[y]<<" "<<v[x]<<"\n";
  333.                     }
  334.                 }
  335.             }
  336.  
  337.             cout<<"\n";
  338.  
  339.         }
  340.  
  341.  
  342.     }
  343. }
  344.  
  345.  
  346.  
  347.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
10 1
6 3 3
stdout
copy 
6 3 3
3 6
5 4
1 2
https://ideone.com/Y2hyM3
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

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!