ulvis.paste.net

Paste Search Dynamic
Recent pastes
size
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6. vector<pair<long long int,long long int > > e,v[570000];
  7. long long int n,m,h,a,b,i,j,k,l,arr[30][30],rr[30][30],x,y,p,q,c,ret=0,edge[30][30],cn,rc;
  8. int main(){
  9.         scanf("%lld %lld %lld",&n,&m,&h);
  10.         for(i=0;i<h;i++)
  11.                 for(j=0;j<n;j++)
  12.                         arr[i][j]=j+1;
  13.         for(i=0;i<m;i++){
  14.                 scanf("%lld %lld",&a,&b);
  15.                 edge[a-1][b-1]=1;
  16.                 if(b>1)
  17.                         edge[a-1][b-2]=1;
  18.                 if(b<n-1)
  19.                         edge[a-1][b]=1;
  20.                 x=arr[a-1][b-1];
  21.                 y=arr[a-1][b];
  22.                 for(j=a-1;j<h;j++){
  23.                         for(k=0;k<n;k++){
  24.                                 if(arr[j][k]==x)
  25.                                         p=k;
  26.                                 if(arr[j][k]==y)
  27.                                         q=k;
  28.                         }
  29.                         swap(arr[j][p],arr[j][q]);
  30.                 }
  31.         }
  32.         rc=0;
  33.         for(i=0;i<n;i++){
  34.                 if(arr[h-1][i]==i+1){
  35.                         rc+=1;
  36.                 }
  37.         }
  38.         if(rc==n){
  39.                 printf("0\n");
  40.                 return 0;
  41.         }
  42.         for(i=0;i<h;i++)
  43.                 for(j=0;j<n-1;j++)
  44.                         if(edge[i][j]==0)
  45.                                 e.push_back(make_pair(i+1,j+1));
  46.         for(i=0;i<e.size();i++)
  47.                 v[i].push_back(e[i]);
  48.         cn=e.size();
  49.         for(i=0;i<e.size()-1;i++){
  50.                 for(j=i+1;j<e.size();j++){
  51.                         if(e[i].first!=e[j].first || (long long int)abs(e[i].second-e[j].second)!=1){
  52.                                 v[cn].push_back(e[i]);
  53.                                 v[cn].push_back(e[j]);
  54.                                 cn+=1;
  55.                         }
  56.                 }
  57.         }
  58.         for(i=0;i<e.size()-2;i++){
  59.                 for(j=i+1;j<e.size()-1;j++){
  60.                         for(k=j+1;k<e.size();k++){
  61.                                 if(e[i].first==e[j].first && (long long int)abs(e[i].second-e[j].second)==1)
  62.                                         continue;
  63.                                 else if(e[j].first==e[k].first && (long long int)abs(e[j].second-e[k].second)==1)
  64.                                         continue;
  65.                                 else if(e[k].first==e[i].first && (long long int)abs(e[k].second-e[i].second)==1)
  66.                                         continue;
  67.                                 v[cn].push_back(e[i]);
  68.                                 v[cn].push_back(e[j]);
  69.                                 v[cn].push_back(e[k]);
  70.                                 cn+=1;
  71.                         }
  72.                 }
  73.         }
  74.         for(i=0;i<cn;i++){
  75. //              printf("v : %lld\n",v[i].size());
  76.                 rc=0;
  77.                 for(j=0;j<h;j++)
  78.                         for(k=0;k<n;k++)
  79.                                 rr[j][k]=arr[j][k];
  80.                 for(j=0;j<h;j++){
  81.                         for(k=0;k<n;k++)
  82.                                 printf(" %lld",rr[j][k]);
  83.                         printf("\n");
  84.                 }
  85.                 for(j=0;j<v[i].size();j++){
  86. //                      printf("vv :: %lld %lld\n",v[i][j].first,v[i][j].second);
  87.  
  88.  
  89.                 x=rr[v[i][j].first-1][v[i][j].second-1];
  90.                 y=rr[v[i][j].first-1][v[i][j].second];
  91.                 for(k=v[i][j].first-1;k<h;k++){
  92.                         for(l=0;l<n;l++){
  93.                                 if(arr[k][l]==x)
  94.                                         p=k;
  95.                                 if(arr[k][l]==y)
  96.                                         q=k;
  97.                         }
  98.                         swap(rr[k][p],rr[k][q]);
  99.                 }
  100.  
  101.                 for(j=0;j<h;j++){
  102.                         for(k=0;k<n;k++)
  103.                                 printf(" %lld",rr[j][k]);
  104.                         printf("\n");
  105.                 }
  106.  
  107.  
  108.                 }
  109.                 for(j=0;j<n;j++)
  110.                         if(rr[h-1][j]==j+1)
  111.                                 rc+=1;
  112.                 if(rc==n){
  113.                         printf("%lld\n",v[i].size());
  114.                         return 0;
  115.                 }
  116.         }
  117.         printf("-1\n");
  118.         return 0;
  119. }
Parsed in 0.020 seconds