fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. #define int long long
  5. #define mkp make_pair
  6. #define pb push_back
  7. #define ff first
  8. #define ss second
  9. #define debug1(a) cout<<a<<endl;
  10. #define debug2(a,b) cout<<a<<' '<<b<<endl;
  11. #define debug3(a,b,c) cout<<a<' '<<b<<' '<<c<<endl;
  12. #define rep(i,n) for(int i=0;i<n;i++)
  13. #define repr(i,a,b)for(int i=a;i<b;i++)
  14. #define repre(i,a,b)for(int i=a;i<=b;i++)
  15. #define pi pair<int,int>
  16. #define pii pair<int,pi>
  17. #define all(v) v.begin(),v.end()
  18. #define pq priority_queue
  19. #define mpq priority_queue<int,vector<int>,greater<int> >
  20. #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  21. using namespace __gnu_pbds;
  22. using namespace std;
  23. typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> orderedSet;
  24. typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> orderedMSet;
  25. //*p.find_by_order(index) return value at index
  26. //p.order_of_key(key) return index
  27. const int maxn=1009;
  28. int dp[maxn];
  29. int arr[maxn][maxn];
  30. int visited[maxn];
  31. int n;
  32. int check(int day)
  33. {
  34.   //cout<<day<<endl;
  35.   repre(i,0,n)dp[i]=1;
  36.   int match=0;
  37.   int c=0;
  38.   while(day--)
  39.   {
  40.     repre(i,0,n)visited[i]=0;
  41.     match=0;
  42.     repre(i,1,n)
  43.     {
  44.       if(dp[i]==n || visited[i]==1)continue;
  45.       int oppo=arr[i][dp[i]];
  46.       if(visited[oppo] || dp[oppo]==n)continue;
  47.       int uskaoppo=arr[oppo][dp[oppo]];
  48.       if(uskaoppo==i)
  49.       {
  50.         visited[i]=1;
  51.         visited[oppo]=1;
  52.         dp[i]++;
  53.         dp[oppo]++;
  54.         if(dp[i]==n)c++;
  55.         if(dp[oppo]==n)c++;
  56.         match=1;
  57.       }
  58.     }
  59.     if(c==n)break;
  60.     if(match==0)return -1;
  61.   }
  62.   if(c==n)return 1;
  63.   return 0;
  64. }
  65. int32_t main()
  66. {
  67.   //freopen("input.txt", "r", stdin);
  68.   //freopen("output.txt", "w", stdout);
  69.   fastio
  70.   cin>>n;
  71.   repre(i,1,n)
  72.   {
  73.     repre(j,1,n-1)
  74.     {
  75.       cin>>arr[i][j];
  76.     }
  77.   }
  78.   int low=1;
  79.   int high=(n*(n-1))/2;
  80.   int temp;
  81.   int flag=0;
  82.   while(low<high)
  83.   {
  84.     int mid=(low+high)/2;
  85.     temp=check(mid);
  86.     if(temp==-1)
  87.     {
  88.       flag=1;
  89.       break;
  90.     }
  91.     if(temp==1)high=mid;
  92.     else low=mid+1;
  93.   }
  94.   if(flag==1)cout<<"-1"<<'\n';
  95.   else
  96.   cout<<low<<'\n';
  97.   return 0;
  98. }
  99.  
Success #stdin #stdout 0s 4304KB
comments (?)
stdin
copy 
4
2 3 4
1 3 4
4 1 2
3 1 2
stdout
copy 
4
https://ideone.com/hiB9kP
language:
C++ (gcc 8.3)
created:
4 years 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!