Stable Matching

Description

There are N SAs and N students. Each SA has to help a student one-to-one. However, each SA has a rank of preference for different students, and each student has a rank of preference for different SAs.

Hong has to make a stable matching table that one SA matches one student. Assume that in a matching table, SA Amatches student a, SA B matches student b. If A prefer b to a, and b prefer A to B, the matching table is not stable.

It's very difficult for Hong to solve the problem. So she asks you to help her. Write a program to make a stable matching table. Give priority to SAs.

Input

The first line contains one integer N which shows the number of SAs. The number of students is N, too.

The next line contains N strings separated by one space. The i-th string shows the name of the i-th SA.

The next line contains N strings z. The i-th string shows the name of the i-th student.

Each of the next N lines contains N strings S_1...S_NS1​...SN​ separated by one space. S_1...S_NS1​...SN​ is a permutation of students' names. The i-th line shows the preference order of the i-th SA. The SA prefers S_iSi​ to S_{i+1}..S_NSi+1​..SN​.

Each of the next N lines contains N strings S_1...S_NS1​...SN​ separated by one space. S_1...S_NS1​...SN​ is a permutation of SAs' names. The i-th line shows the preference order of the i-th student. The student prefers S_iSi​ to S_{i+1}..S_NSi+1​..SN​.

The length of each string \leq≤ 10.

Output

Output a line contains N strings. The i-th string S_iSi​ means that the i-th SA matches student S_iSi​.

Sample Input 1

3
adam bale campbell
alice bob calvin
bob calvin alice
calvin bob alice
bob alice calvin
adam bale campbell
adam campbell bale
bale adam campbell

Copy

Sample output 1

bob calvin alice

Copy

Sample Input 2

5
adam bale campbell daisy eddy
alice bob calvin david emily
david calvin alice emily bob
bob alice calvin david emily
alice emily david calvin bob
alice calvin david bob emily
alice bob calvin david emily
campbell bale adam daisy eddy
eddy daisy bale adam campbell
daisy bale adam campbell eddy
campbell daisy adam eddy bale
bale adam eddy campbell daisy

Copy

Sample Output 2

david emily alice calvin bob

Copy

Limit

1 second for each test case. The memory limit is 256MB.
For 100% test cases, N \leq≤ 1000.

 

Solution

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.io.InputStream;
import java.util.HashMap;
import java.util.Stack;
import java.util.StringTokenizer;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args) throws IOException{
		InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        
        int N = in.nextInt();
        String[] SAName = new String[N+1];
        String[] studentName = new String[N+1];
        HashMap<String, Integer> SAIndex = new HashMap<String, Integer>();
        HashMap<String, Integer> studentIndex = new HashMap<String, Integer>();
        
        String p = null;
        for(int i = 1; i < N+1; i++) {
        	p = in.next();
        	SAName[i] = p;
        	SAIndex.put(p, i);
        }
        for(int i = 1; i < N+1; i++) {
        	p = in.next();
        	studentName[i] = p;
        	studentIndex.put(p, i);
        }
        
        int[][] SAPrefernce = new int[N+1][N+1];
        //Put 1 at the 0 cell for all the prefernce list.
        for(int i = 1; i < N+1; i++) {
        	SAPrefernce[i][0] = 1;
        }
        
        int[][] studentPrefernce = new int[N+1][N+1];
        
        //read the rest of the input
        //SAPrefernce list
        for(int x = 1; x < N+1; x++) {
        	for(int y = 1; y < N+1; y++) {
        		p = in.next();
        		SAPrefernce[x][y] = studentIndex.get(p);
        	}
        }
      
        //studentPrefernce list
        for(int x = 1; x < N+1; x++) {
        	for(int y = 1; y < N+1; y++) {
        		p = in.next();
        		studentPrefernce[x][y] = SAIndex.get(p);
        	}
        }
        
        String[] ANS = stableMatching(SAName, studentName, SAPrefernce, studentPrefernce);
        
        for(String s : ANS)
        	out.print(s+" ");
        out.println();
        out.close();
	}
    public static String[] stableMatching(String[] SAName,         //SAIndex -> Name
    									  String[] studentName,    //StudentIndex -> Name
    								      int[][] SAPrefernce,      //SAIndex -> ( rank_number -> studentIndex )
    									  int[][] studentPrefernce  //studentIndex -> ( rank_number -> SAIndex ) 
    									  ) {
    	int N = SAName.length - 1;
    	
    	//Initialization
    	int[] student_current_partner = new int[N+1]; //studentIndex -> SAIndex
    	int[] SA_current_partner = new int[N+1]; //SAIndex -> StudentIndex
    	
    	int[][] SA_in_student_prefernce = new int[N+1][N+1]; //studentIndex-> ( SAIndex -> SA_rank )
    	for(int i = 1; i < N+1; i++) {
    		int[] student_i_preference = studentPrefernce[i];//rank_number -> SAIndex
    		for(int n = 1; n < N+1; n++) {
    			SA_in_student_prefernce[i][student_i_preference[n]] = n; 
    		}
    	}
    	
    	Stack<Integer> stack = new Stack<Integer>();
    	for(int i = 1; i < N+1; i++)
    		stack.push(i);
    	
    	//Build matching
    	while(!stack.isEmpty()) {
    		int SA = stack.pop();
    		int current_index = SAPrefernce[SA][0];
    		int aim = SAPrefernce[SA][current_index];
    		SAPrefernce[SA][0] = SAPrefernce[SA][0] + 1;
    		
    		int aim_current_partner = student_current_partner[aim];
    		
    		if(aim_current_partner == 0) {
    			student_current_partner[aim] = SA;
    			SA_current_partner[SA] = aim;
    		}else {
    			if(SA_in_student_prefernce[aim][SA] < SA_in_student_prefernce[aim][aim_current_partner]) {
    				//pair up
    				student_current_partner[aim] = SA;
    				SA_current_partner[SA] = aim;
    				
    				stack.push(aim_current_partner);
    				SA_current_partner[aim_current_partner] = 0;
    			}else {
    				stack.push(SA);
    			}
    		}

    	}
    	
    	String[] ans = new String[N];
    	for(int i = 1; i < N+1; i++) {
    		ans[i-1] = studentName[SA_current_partner[i]];
    	}
    	return ans;
    }
/////////////////////////////////////////////////////////////////////////////////////    
	
	static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
        
        public double nextDouble() {
            return Double.parseDouble(next());
        }
        
        public char[] nextCharArray() {
            return next().toCharArray();
        }
        
        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
        
        public BigDecimal nextBigDecimal() {
            return new BigDecimal(next());
        }
        
    }
  
} 

 

上一篇:linux安装chrome浏览器


下一篇:sort和stable_sort