团体程序设计天梯赛 L2-028. 秀恩爱分得快

时间:2021-04-23 10:46:52

1.输入-0(第一部分、第二部分),输出-0
2.只统计与两个人的亲密程度,否则超时

 

Data:

4 1
4 -0 1 -2 3
-0 1

-0 1

------

4 1

3 1 -2 3
-0 1

-0 1
-0 3
1 -2

------

4 2
4 -0 1 -2 3
2 -0 3
1 -0

1 -0
1 -2
-0 3

 

  1 /*
  2 1.输入-0(第一部分、第二部分),输出-0
  3 2.只统计与两个人的亲密程度,否则超时 
  4 */
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <cstring>
  8 #include <cmath>
  9 #include <stdbool.h>
 10 #include <set>
 11 #include <vector>
 12 #include <map>
 13 #include <algorithm>
 14 using namespace std;
 15 
 16 double f[2][1005];
 17 long d[1005][505],sex[1005],g[1005];
 18 
 19 void print(long x,long y)
 20 {
 21     if (x==0 && sex[x]==-1)
 22         printf("-0");
 23     else
 24         printf("%ld",x*sex[x]);
 25     printf(" ");        
 26     if (y==0 && sex[y]==-1)
 27         printf("-0");
 28     else
 29         printf("%ld",y*sex[y]);
 30     printf("\n");
 31 }
 32 
 33 bool pan(double x,double y)
 34 {
 35     if (fabs(x-y)<0.0000001)
 36         return true;
 37     else
 38         return false;
 39 }
 40 
 41 bool pan1(double x,double y)
 42 {
 43     if (fabs(x-y)<0.0000001)
 44         return true;
 45     if (x>y)
 46         return true;
 47     else
 48         return false;    
 49 }
 50 
 51 int main()
 52 {
 53     char s[10];
 54     long n,m,i,j,k,x,y,w;
 55     double v1,v2;
 56     scanf("%ld%ld",&n,&m);
 57     for (i=0;i<=1;i++)
 58         for (j=0;j<n;j++)
 59             f[i][j]=0;
 60     for (k=1;k<=m;k++)
 61     {
 62         scanf("%ld",&g[k]);
 63         for (i=1;i<=g[k];i++)
 64         {
 65             scanf("%s",s);
 66             if (s[0]=='-')
 67             {
 68                 w=strlen(s);
 69                 strncpy(s,s+1,w-1);
 70                 s[w-1]='\0';
 71                 d[k][i]=atoi(s);
 72                 sex[d[k][i]]=-1;
 73             }
 74             else
 75             {
 76                 d[k][i]=atoi(s);
 77                 sex[d[k][i]]=1;
 78             }
 79         }
 80     }
 81     
 82     scanf("%s",s);
 83     if (s[0]=='-')
 84     {
 85         w=strlen(s);
 86         strncpy(s,s+1,w-1);
 87         s[w-1]='\0';
 88         x=atoi(s);
 89         sex[x]=-1;
 90     }
 91     else
 92     {
 93         x=atoi(s);
 94         sex[x]=1;
 95     }
 96     
 97     scanf("%s",s);
 98     if (s[0]=='-')
 99     {
100         w=strlen(s);
101         strncpy(s,s+1,w-1);
102         s[w-1]='\0';
103         y=atoi(s);
104         sex[y]=-1;
105     }
106     else
107     {
108         y=atoi(s);
109         sex[y]=1;
110     }
111     
112     for (k=1;k<=m;k++)
113     {
114         for (i=1;i<=g[k];i++)
115             if (d[k][i]==x)
116             {
117                 for (j=1;j<=g[k];j++)
118                     if (sex[d[k][i]]+sex[d[k][j]]==0)
119                         f[0][d[k][j]]+=1.0/g[k];
120             }
121                         
122         for (i=1;i<=g[k];i++)
123             if (d[k][i]==y)
124             {
125                 for (j=1;j<=g[k];j++)
126                     if (sex[d[k][i]]+sex[d[k][j]]==0)
127                         f[1][d[k][j]]+=1.0/g[k];
128             }        
129     }
130     
131     v1=0;
132     for (i=0;i<n;i++)
133         v1=max(v1,f[0][i]);
134     
135     v2=0;
136     for (i=0;i<n;i++)
137         v2=max(v2,f[1][i]);
138 
139     if (pan(v1,f[0][y]) && pan(v2,f[1][x]))
140         print(x,y);
141     else
142     {
143         //maybe maximum=0, double wrong(guess)
144         for (i=0;i<n;i++)
145             if (pan1(f[0][i],v1) && sex[i]+sex[x]==0)
146                 print(x,i);
147         for (i=0;i<n;i++)
148             if (pan1(f[1][i],v2) && sex[y]+sex[i]==0)
149                 print(y,i);
150     }
151     return 0;
152 }
153 /*
154 4 1
155 4 -0 1 -2 3
156 -0 1
157 
158 -0 1
159 
160 ------
161 
162 4 1
163 3 1 -2 3
164 -0 1
165 
166 -0 1
167 -0 3
168 1 -2
169 
170 ------
171 
172 4 2
173 4 -0 1 -2 3
174 2 -0 3
175 1 -0
176 
177 1 -0
178 1 -2
179 -0 3
180 */