题目链接:http://codeforces.com/contest/733/problem/D
用map<pair<int, int>int>标记(第一次用~)…
代码:
1 #include <bits/stdc++.h>
2 #define MAXN 100001
3 using namespace std;
4
5 typedef pair<int, int> pair1;
6 typedef map<pair1, int> map1;
7
8 struct gg{
9 int x, y;
10 int xx, yy;
11 int xxx, yyy;
12 }jj[MAXN*3];
13
14 int main(void){
15 int n, k=1;
16 map1 mp;
17 for(int i=0; i<MAXN; i++){
18 jj[i].x=jj[i].y=jj[i].xx=jj[i].yy=jj[i].xxx=jj[i].yyy=0;
19 }
20 scanf("%d", &n);
21 for(int i=1; i<=n; i++){
22 int a[3], ok1=0, ok2=0, ok3=0;
23 scanf("%d%d%d", &a[0], &a[1], &a[2]);
24 sort(a, a+3);
25 if(a[0]==a[2]){
26 ok1=1;
27 }
28 if(a[0]==a[1]){
29 ok2=1;
30 }
31 if(a[1]==a[2]){
32 ok3=1;
33 }
34 int flag1=mp[pair1(a[0], a[1])];
35 if(flag1==0){
36 jj[k].x=a[0];
37 jj[k].y=a[1];
38 jj[k].xx=a[2];
39 jj[k].xxx=i;
40 mp[pair1(a[0], a[1])]=k;
41 k++;
42 }else{
43 if(jj[flag1].xx>jj[flag1].yy){
44 swap(jj[flag1].xx, jj[flag1].yy);
45 swap(jj[flag1].xxx, jj[flag1].yyy);
46 }
47 if(jj[flag1].xx<a[2]){
48 jj[flag1].xx=a[2];
49 jj[flag1].xxx=i;
50 }
51 }
52 if(ok1){
53 continue;
54 }
55 if(!ok3){
56 int flag2=mp[pair1(a[0], a[2])];
57 if(flag2==0){
58 jj[k].x=a[0];
59 jj[k].y=a[2];
60 jj[k].xx=a[1];
61 jj[k].xxx=i;
62 mp[pair1(a[0], a[2])]=k;
63 k++;
64 }else{
65 if(jj[flag2].xx>jj[flag2].yy){
66 swap(jj[flag2].xx, jj[flag2].yy);
67 swap(jj[flag2].xxx, jj[flag2].yyy);
68 }
69 if(jj[flag2].xx<a[1]){
70 jj[flag2].xx=a[1];
71 jj[flag2].xxx=i;
72 }
73 }
74 }
75 if(ok2){
76 continue;
77 }
78 int flag3=mp[pair1(a[1], a[2])];
79 if(flag3==0){
80 jj[k].x=a[1];
81 jj[k].y=a[2];
82 jj[k].xx=a[0];
83 jj[k].xxx=i;
84 mp[pair1(a[1], a[2])]=k;
85 k++;
86 }else{
87 if(jj[flag3].xx>jj[flag3].yy){
88 swap(jj[flag3].xx, jj[flag3].yy);
89 swap(jj[flag3].xxx, jj[flag3].yyy);
90 }
91 if(jj[flag3].xx<a[0]){
92 jj[flag3].xx=a[0];
93 jj[flag3].xxx=i;
94 }
95 }
96 }
97 int cc=0, dd=0, ee=0;
98 for(int i=1; i<k; i++){
99 int cnt=min(jj[i].x, jj[i].y);
100 cnt=min(cnt, jj[i].xx+jj[i].yy);
101 if(cc<cnt){
102 cc=cnt;
103 dd=jj[i].xxx;
104 ee=jj[i].yyy;
105 }
106 }
107 if(dd&&ee){
108 printf("2
%d %d
", dd, ee);
109 }else{
110 printf("1
%d
", dd+ee);
111 }
112 return 0;
113 }
最新评论