fork download
  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
stdin
4
2 3 4
1 3 4
4 1 2
3 1 2
stdout
4