fork(1) download
copy 
  1. import java.util.*;
  2.  
  3. class A_WorldFootballCup {
  4. 	public static void main(String[] args) throws Exception {
  5. 		Scanner scan = new Scanner(System.in);
  6. 		int n = new Integer(scan.nextLine());
  7. 		List<String> names = new ArrayList<String>();
  8. 		Map<String, Integer> r1 = new HashMap<String, Integer>();
  9. 		Map<String, Integer> r2 = new HashMap<String, Integer>();
  10. 		Map<String, Integer> r3 = new HashMap<String, Integer>();
  11. 		for (int i = 0; i < n; ++i) {
  12. 			String s = scan.next();
  13. 			names.add(s);
  14. 			r1.put(s, 0);
  15. 			r2.put(s, 0);
  16. 			r3.put(s, 0);
  17. 		}
  18. 		for (int i = n * (n - 1) / 2; i-- > 0;) {
  19. 			String[] s = scan.next().split("-");
  20. 			String[] t = scan.next().split(":");
  21. 			int t0 = new Integer(t[0]);
  22. 			int t1 = new Integer(t[1]);
  23. 			r1.put(s[0], r1.get(s[0])+(t0>t1?3:t0==t1?1:0));
  24. 			r1.put(s[1], r1.get(s[1])+(t1>t0?3:t0==t1?1:0));
  25. 			r2.put(s[0], r2.get(s[0])+t0-t1);
  26. 			r2.put(s[1], r2.get(s[1])+t1-t0);
  27. 			r3.put(s[0], r3.get(s[0])+t0);
  28. 			r3.put(s[1], r3.get(s[1])+t1);
  29. 		}
  30.  
  31. 		Set<String>result = new TreeSet<String>();
  32.  
  33. 		Map<Integer, List<String>> vics = new TreeMap<Integer, List<String>>(Collections.reverseOrder());
  34. 		for(String name : names){
  35. 			int i = r1.get(name);
  36. 			if(!vics.containsKey(i)){
  37. 				vics.put(i, new ArrayList<String>());
  38. 			}
  39. 			vics.get(i).add(name);
  40. 		}
  41.  
  42. 		l:for(int i : vics.keySet()){
  43. 			List<String> list = vics.get(i);
  44. 			if(result.size() + list.size() <= n/2){
  45. 				result.addAll(list);
  46. 			}else{
  47. 				Map<Integer, List<String>> subs = new TreeMap<Integer, List<String>>(Collections.reverseOrder());
  48. 				for(String name : list){
  49. 					int j = r2.get(name);
  50. 					if(!subs.containsKey(j)){
  51. 						subs.put(j, new ArrayList<String>());
  52. 					}
  53. 					subs.get(j).add(name);
  54. 				}
  55. 				for(int j : subs.keySet()){
  56. 					List<String> list2 = subs.get(j);
  57. 					if(result.size() + list2.size() <= n/2){
  58. 						result.addAll(list2);
  59. 					}else{
  60. 						Map<Integer, List<String>> sums = new TreeMap<Integer, List<String>>(Collections.reverseOrder());
  61. 						for(String name : list2){
  62. 							int k = r3.get(name);
  63. 							if(!sums.containsKey(i)){
  64. 								sums.put(k, new ArrayList<String>());
  65. 							}
  66. 							sums.get(k).add(name);
  67. 						}
  68. 						while(result.size() < n/2){
  69. 							List<String> list3 = sums.get(new ArrayList<Integer>(sums.keySet()).get(0));
  70. 							result.addAll(list3.subList(0, Math.min(list3.size(), n/2-result.size())));
  71. 						}
  72. 						break l;
  73. 					}
  74. 				}
  75. 				break l;
  76. 			}
  77. 		}
  78.  
  79. 		for(String name : result){
  80. 			System.out.println(name);
  81. 		}
  82. 	}
  83. }
  84.  
Success #stdin #stdout 0.06s 213888KB
comments (?)
stdin
copy 
4
A
B
C
D
A-B 1:1
A-C 2:2
A-D 1:0
B-C 1:0
B-D 0:3
C-D 0:3
stdout
copy 
A
D
https://ideone.com/MOdCy
language:
Java (HotSpot 12)
created:
15 years ago
visibility:
secret

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!