fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. // Men and women are represented by integers 1...N
  7.  
  8. // ManPref is the preference list of all men for all women.
  9. // ManPref[m][i] = w iff w is at ith position in the preference list of m
  10.  
  11. // WomanPref is the preference list of all women for all men.
  12. // WomanPref[w][i] = m iff m is at ith position in the preference list of w
  13.  
  14. // Ranking gives the ranking of each man in the preference list of each woman
  15. // Ranking[w][m] = i iff WomanPref[w][i] = m
  16.  
  17. // Current gives the current engagement of each women
  18. // Current[w] = m iff w is currently engaged to m
  19.  
  20. // Next gives the index of next woman to propose to in the preference list of each man
  21. // Next[m] = i iff m has proposed to all w s.t. ManPref[m][j] = w for j = 1...i-1 but not ManPref[m][i]
  22. int Ranking[505][505], ManPref[505][505], WomanPref[505][505], Next[505], Current[505];
  23.  
  24. int main()  {
  25.     int T, N, i, j, m, w;
  26.  
  27.     // list of men who are not currently engaged
  28.     queue <int> freeMen;
  29.  
  30.     scanf("%d", &T);    // No. of test cases
  31.     while (T--) {
  32.         scanf("%d", &N);    // No. of men and women
  33.         for (i = 1; i <= N; i++) {
  34.             scanf("%d", &w);    // Woman number (b/w 1 and N) followed by her preference list
  35.             for (j = 1; j <= N; j++)
  36.                 scanf("%d", &WomanPref[w][j]);
  37.         }
  38.         for (i = 1; i <= N; i++) {
  39.             scanf("%d", &m);    // Man number (b/w 1 and N) followed by his preference list
  40.             for (j = 1; j <= N; j++)
  41.                 scanf("%d", &ManPref[m][j]);
  42.         }
  43.  
  44.         for (i = 1; i <= N; i++)
  45.             for (j = 1; j <= N; j++)
  46.                 Ranking[i][WomanPref[i][j]] = j;
  47.  
  48.         memset(Current, 0, (N + 1) * sizeof(int));
  49.  
  50.         for (i = 1; i <= N; i++) {
  51.             freeMen.push(i);
  52.             Next[i] = 1;
  53.         }
  54.  
  55.         while (!freeMen.empty())    {
  56.             m = freeMen.front();
  57.             w = ManPref[m][Next[m]++];
  58.             if (Current[w] == 0)   {
  59.                 Current[w] = m;
  60.                 freeMen.pop();
  61.             } else if (Ranking[w][m] < Ranking[w][Current[w]])  {
  62.                 freeMen.pop();
  63.                 freeMen.push(Current[w]);
  64.                 Current[w] = m;
  65.             }
  66.         }
  67.  
  68.         // (m, w) pairs in the stable matching
  69.         for (w = 1; w <= N; w++)
  70.             printf("%d %d\n", Current[w], w);
  71.     }
  72.  
  73.     return 0;
  74. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
1

5
5 1 3 2 4
3 4 1 2 5
5 4 2 1 3
4 1 2 3 5
1 2 3 4 5
2 3 1 4 5
3 1 5 2 4
2 3 4 5 2
3 2 5 4 1
3 1 2 5 4
stdout
copy 
4 1
0 2
5 3
3 4
2 5
https://ideone.com/dhSFuG
language:
C++ (gcc 8.3)
created:
36 days 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!