SuitNdtie

Bathroom set1

Apr 8th, 2019
195
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.95 KB | None | 0 0
  1. #include<stdio.h>
  2. int min(int a,int b){
  3.     return (a < b ? a : b);
  4. }
  5. int max(int a,int b){
  6.     return (a > b ? a : b);
  7. }
  8. bool debug = false;
  9. int main()
  10. {
  11.     int T;
  12.     scanf("%d",&T);
  13.     for(int _ = 1 ; _ <= T ; _ ++){
  14.         int ansls;
  15.         int ansrs;
  16.         int n,k;
  17.         scanf("%d %d",&n,&k);
  18.         bool br[n+2]; for(int i=0;i<n+2;i++) br[i] = false;
  19.         br[0] = true;br[n+1] = true;
  20.         for(int p = 1 ; p <= k ; p ++){
  21.             int minlr = -1;
  22.             int cntidx = 0;
  23.             int idx[n+2];
  24.             int lofp[n+2];
  25.             int rofp[n+2];
  26.             for(int i=1;i<=n;i++){
  27.                 int l = i,r = i;
  28.                 while(!br[l])l--;
  29.                 while(!br[r])r++;
  30.                 lofp[i] = i - l - 1;
  31.                 rofp[i] = r - i - 1;
  32.                 l = i - l - 1;
  33.                 r = r - i - 1;
  34.                 if(min(l,r) >= minlr){
  35.                     if(min(l,r) == minlr){
  36.                         cntidx++;
  37.                         idx[cntidx] = i;
  38.                     }
  39.                     else{
  40.                         cntidx = 0;
  41.                         idx[0] = i;//min(l,r);
  42.                     }
  43.                     minlr = min(l,r);
  44.                 }
  45.             }
  46.             if(debug){
  47.                 printf("Test %d\n",cntidx);
  48.                 for(int i=0;i<=cntidx;i++){
  49.                     printf("%d ",idx[i]);
  50.                 }
  51.                 printf("\n");
  52.                
  53.             }
  54.             if(cntidx >= 1){
  55.                 int maxlr = -1;
  56.                 int ans;
  57.                 bool more = false;
  58.                 for(int i=0;i<=cntidx;i++){
  59.                     if(debug)printf("Test %d (%d,%d)\n",idx[i],lofp[idx[i]],rofp[idx[i]]);
  60.                     maxlr = max(maxlr,max(lofp[idx[i]],rofp[idx[i]]));
  61.                 }
  62.                
  63.                 int cntlm = 0;
  64.                 for(int i=0;i<=cntidx;i++){
  65.                     if(max(lofp[idx[i]],rofp[idx[i]]) == maxlr){
  66.                         cntlm++;
  67.                         if(cntlm >= 2){
  68.                             br[ans] = true;
  69.                             ansls = lofp[ans];
  70.                             ansrs = rofp[ans];
  71.                             break;
  72.                         }
  73.                         ans = idx[i];
  74.                     }
  75.                 }
  76.                 if(cntlm == 1){
  77.                     br[ans] = true;
  78.                     ansls = lofp[ans];
  79.                     ansrs = rofp[ans];
  80.                 }
  81.             }else{
  82.                 br[idx[0]] = true;
  83.                 ansls = lofp[idx[0]];
  84.                 ansrs = rofp[idx[0]];
  85.             }
  86.             if(debug){
  87.                 printf("Test\n");
  88.                 for(int i=0;i<n+2;i++){
  89.                     printf("%d ",br[i]);
  90.                 }
  91.                 printf("\n");
  92.                
  93.             }
  94.         }
  95.         printf("Case #%d: %d %d\n",_,max(ansls,ansrs),min(ansls,ansrs));
  96.     }
  97. }
Advertisement
Add Comment
Please, Sign In to add comment