fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define REP(i,a,b) for(i=a;i<b;i++)
  5. #define rep(i,n) REP(i,0,n)
  6.  
  7. #define mygc(c) (c)=getchar_unlocked()
  8. void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
  9. template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
  10.  
  11. int T, C;
  12. int N, R, G;
  13. int RP[110000], RV[110000], GP[110000], GV[110000], P[110000];
  14.  
  15. int solve(void){
  16.   int i, j, k, p, c;
  17.   int a, b;
  18.   int t, res = -1;
  19.   int mn, mx, t1, t2;
  20.  
  21.   double dt = 0;
  22.  
  23.   if(GV[0]+RV[0]==0){
  24.     k = RP[0];
  25.   } else {
  26.     if(GP[0] > RP[0]) dt = (double)(GP[0] - RP[0]) / (GV[0] + RV[0]);
  27.     k = (int)(RP[0] + dt * RV[0]);
  28.   }
  29.  
  30.   rep(i,N) if(k < P[i]) break;
  31.   c = i;
  32.  
  33.   P[N] = 1000000000;
  34.  
  35.   REP(p,c-1,c+2){
  36.     if(p < 0 || p >= N) continue;
  37.     a = P[p];
  38.     b = P[p+1];
  39.  
  40.     mn = 0;
  41.     mx = 1000000001;
  42.  
  43.     rep(i,R){
  44.       if(RV[i]==0){
  45.         if(a <= RP[i] && RP[i] <= b) continue;
  46.         mn = 1; mx = 0;
  47.         break;
  48.       }
  49.       t1 = (a - RP[i]) / RV[i];
  50.       while(RP[i] + RV[i]*t1 < a) t1++;
  51.       t2 = (b - RP[i]) / RV[i];
  52.       while(RP[i] + RV[i]*(t2+1) <= b) t2++;
  53.  
  54.       mn = max(mn, t1);
  55.       mx = min(mx, t2);
  56.     }
  57.  
  58.     rep(i,G){
  59.       if(GV[i]==0){
  60.         if(a <= GP[i] && GP[i] <= b) continue;
  61.         mn = 1; mx = 0;
  62.         break;
  63.       }
  64.       t1 = (GP[i] - b) / GV[i];
  65.       while(GP[i] - GV[i]*t1 > b) t1++;
  66.       t2 = (GP[i] - a) / GV[i];
  67.       while(GP[i] - GV[i]*(t2+1) >= a) t2++;
  68.  
  69.       mn = max(mn, t1);
  70.       mx = min(mx, t2);
  71.     }
  72.  
  73.     if(mn > mx) continue;
  74.     if(res==-1 || res > mn) res = mn;
  75.   }
  76.  
  77.   return res;
  78. }
  79.  
  80. int main(){
  81.   int i, res;
  82.  
  83.   reader(&T);
  84.   while(T--){
  85.     reader(&R,&G,&N);
  86.     N++;
  87.     rep(i,R) reader(RP+i);
  88.     rep(i,R) reader(RV+i);
  89.     rep(i,G) reader(GP+i);
  90.     rep(i,G) reader(GV+i);
  91.     REP(i,1,N) reader(P+i);
  92.  
  93.     res = solve();
  94.     printf("Case %d: %d\n",++C,res);
  95.   }
  96.  
  97.   return 0;
  98. }
  99.  
Time limit exceeded #stdin #stdout 5s 5608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/phYuDN
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

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!