/**
 ============================================================================
 【问题描述】
 有这么一个速配电视节目。N位男士和N位女士要在摄像机前选出他们合适的伴侣。每位女士按照其对
 每位男士作为配偶的偏爱程度给每位男士排名次，每位男士也按照其对每位女士作为配偶的偏爱程度给每位
 女士排名次。这些名次不允许并列。然后每位男士将向心仪的对象求婚，经过"残酷"的竞争之后各自找到适
 合的伴侣。最开始的时候每位男士都还没有被任何一位女士拒绝。求婚环节会经过很多轮进行，每一轮：
 (1) 每位男士在还没有拒绝过自己的女士中选出自己认为最理想的一个，并向她求婚
 (2) 每位女士在所有这一轮中向她求婚的男士中选出自己认为最理想的一个，并不答应，也不拒绝。
 她把其余向她求婚的男士都婉言拒绝掉。经过了若干轮求婚之后，在某一轮，幸运的事情发生了：所有的女
 士都恰好有一个求婚者，所有的男士都找到一个心仪的对象。主持人将继续指出这个配对方式的神奇之处：
 没有任意的两个配对，比方说男士A和女士a配对,男士B和女士b配对，使得在A心目中b较a更理想，而且在
 b心目中A较B更理想（这样A和b就会"私奔"）。因此，主持人总结说，这个配对是非常合理的。（他知道，
 这种情况是一定会发生的。）
 主持人在节目之前已经知道男士和女士之间的偏爱情况，他想预先知道最后的匹配结果是怎么样的，
 你能帮帮他吗？
 【要求】
 【数据输入】
 第一行包括一个数字N（1<=N<=1000）以下N*2行，每行有N个数字。第i+1行（1<=i<=N）表示编
 号为i的男士对女士们的排序（从最喜欢的到最不喜欢的）。第N+j+1行（1<=j<=N）表示编号为j的女士
 对男士们的排序（同样从最喜欢的到最不喜欢的）。
 【数据输出】
 N行，每行包括一个数字。第i行的数字表示与编号为i的男士匹配的女士的编号。
 【样例输入】
 3
 1 2 3
 2 3 1
 2 1 3
 3 2 1
 2 3 1
 2 3 1
 【样例输出】
 3
 2
 1
 =============================================================================
 **/

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define N 10

// 找到 第n位男士当前最中意且未被拒绝过的女士
void findWoman(int sa[N][N], int mostLike[N])
{
    for (int i = 0;i < N;i++)
    {
        int pos = 0, ans = sa[i][0];
        for (int j = 0;j < N;j++)
        {
            if (ans < sa[i][j]) pos = j, ans = sa[i][pos];
        }
        printf("%5d号男士对%5d号女士求婚\n", i + 1, mostLike[i] = pos + 1);
    }
    printf("\n");
}

// 获取当前求婚状态
bool getState(int state[N][N + 1], int mostLike[N])
{
    bool ans = true;
    for (int i = 0;i < N;i++)
    {
        state[i][0] = 0;
        for (int j = 0;j < N;j++)
        {
            if (mostLike[j] == i + 1) state[i][++state[i][0]] = j + 1;
        }
        if (state[i][0] != 1) ans = false;
    }

    return ans;
}

// 找到对女士求婚者中最被中意的人
void findMostLike(int sb[N][N], int state[N][N + 1], int mostLike[N])
{
    // 找到女士的求婚者中最中意的男士
    for (int i = 0;i < N;i++)
    {
        int tm = -1, tn = -1;
        for (int j = state[i][0];j > 0;j--)
        {
            if (sb[i][state[i][j] - 1] > tn)
            {
                tm = state[i][j];
                tn = sb[i][tm - 1];
            }
        }
        mostLike[i] = tm;

        if (mostLike[i] != -1)
        {
            printf("%5d号女士中意%5d号男士\n", i + 1, tm);
        }
        else
        {
            printf("%5d号女士没有中意人选\n", i + 1);
        }
    }
    printf("\n");
}

// 根据男士的选择，女士将不是最满意的拒绝
void refuseMan(int sa[N][N], int state[N][N + 1], int mostLike[N])
{
    // 将其他男士拒绝
    for (int i = 0;i < N;i++)
    {
        for (int j = state[i][0];j > 0;j--)
        {
            if (mostLike[i] != state[i][j])
            {
                printf("%5d号女士拒绝了%5d号男士\n", i + 1, state[i][j]);
                sa[state[i][j] - 1][i] = -1;
            }
        }
    }
    printf("\n");
}

// 打印最终结果
void print(int state[N][N + 1])
{
    for (int i = 0;i < N;i++)
    {
        printf("%5d号男士选择了%5d号女士\n", state[i][1], i + 1);
    }
}

// 根据数据地址对数据数值交换
void swap(int *pa, int *pb)
{
    int tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}

// 生成测试数据
void initArray(int sa[N][N], int sb[N][N])
{
    srand(time(NULL));
    for (int i = 0;i < N;i++)
    {
        for (int j = 0;j < N;j++)
        {
            sa[i][j] = sb[i][j] = j + 1;
        }

        for (int j = N - 1;j > 0;j--)
        {
            int ta = rand() % j;
            swap(&sa[i][j], &sa[i][ta]);

            int tb = rand() % j;
            swap(&sb[i][j], &sb[i][tb]);
        }
    }

    for (int i = 0;i < N;i++)
    {
        for (int j = 0;j < N;j++)
        {
            printf("%5d", sa[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    for (int i = 0;i < N;i++)
    {
        for (int j = 0;j < N;j++)
        {
            printf("%5d", sb[i][j]);
        }
        printf("\n");
    }
}

// 主函数
int main()
{
    int sa[N][N] = { { 0 } };
    int sb[N][N] = { { 0 } };

    int mostLike[N] = { 0 };  // mostLike[n]记录当前第n+1位男士最中意的女士
    int state[N][N + 1] = { { 0 } }; // state[n]记录当时会对第n位女士求婚的男士,state[n][0]表示人数

    initArray(sa, sb);
    while (true)
    {
        findWoman(sa, mostLike);

        if (getState(state, mostLike)) break;

        findMostLike(sb, state, mostLike);

        refuseMan(sa, state, mostLike);
    }
    print(state);
    return 0;
}