714 - Copying Books

[viniciusweb]

Thanks Jan! I got AC after fixing some problems with overflow...

[coze]

I've got the right output for the simple input, but the result of submission is WA.

Can you tell me what is your output with this input ?

Input:

Code: Select all

3
12 5
48 65 53 3 90 3 90 30 52 75 54 22
10 4
82 36 6 11 33 33 25 79 9 7
9 5
64 16 75 91 1 71 43 81 13

My WA output:

Code: Select all

48 65 / 53 3 90 / 3 90 30 / 52 75 / 54 22
82 / 36 6 11 / 33 33 25 / 79 9 7
64 / 16 75 / 91 1 / 71 43 / 81 13

[viniciusweb]

coze, my AC code produces the same output.

[coze]

Thank you, viniciusweb. I got AC now.

[bourne]

I am getting correct result for all the test cases posted in this thread. Still I am getting WA at the judge. I used the binary search + greedy approach as discussed in this thread. Can someone figure out my mistake or post some more tricky cases?

Code: Select all

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<sstream>
#include<map>
#include<stack>
#include<set>
#include<cmath>
#include<iomanip>
using namespace std;
#define PB push_back
#define vi vector<int>
#define LL long long
#define all(v) v.begin(),v.end()
#define GI ({int t ; scanf("%d",&t);t;})

int M,K;
int A[500];
bool go(LL maxsum)
{
   LL sum=0;
   int k=1;
   for(int i=0;i<M;i++)
   {
      if(sum+A[i]>maxsum){
         sum=A[i];
         k++;
      }
      else
         sum+=A[i];
   }
   return (sum<=maxsum && k<=K);
}
void print(LL maxsum)
{
   int k=1;
   vi res;
   res.PB(A[M-1]);
   LL sum=A[M-1];
   for(int i=M-2;i>=0;i--)
   {
      if(sum+A[i]>maxsum){
         res.PB(-1);
         res.PB(A[i]);
         sum=A[i];
         k++;
      }
      else{
         res.PB(A[i]);
         sum+=A[i];
      }   
   }
   reverse(all(res));
   

   while(k<K)
   {
      for(int i=1;i<res.size();i++)
         if(res[i-1]!=-1 && res[i]!=-1){
            res.insert(res.begin()+i,-1);
            k++;
            break;
         }   
   }

   printf("%d",res[0]);
   for(int i=1;i<res.size();i++)
   {
      if(res[i]==-1)
         printf(" /");
      else
         printf(" %d",res[i]);
   }
   printf("\n");      
}
int main()
{
   int t=GI;
   while(t--)
   {
      M=GI; K=GI;
      for(int i=0;i<M;i++) A[i]=GI;
      
      LL lo=0,hi=1LL<<40;
      for(int i=0;i<50;i++)
      {
         LL mid=(lo+hi)/2;
         if(go(mid))
            hi=mid;
         else
            lo=mid;
      }
      print(hi);
   }
}


[Angeh]

1
6 3
8 3 5 4 1 10

Angeh

[brianfry713]

Input:

Code: Select all

10
68 26
31730 22830 3272 4144 16256 20385 2435 13740 20324 10870 27414 4722 11245 10638 15417 29839 19155 4537 26608 21387 25380 26684 21840 20034 3058 27140 29714 10883 6590 15014 1497 12906 26275 1822 12355 2942 28994 6212 9137 25481 32369 4365 25303 3899 10659 21639 30466 30333 4117 20370 7468 27286 702 8799 14273 16896 27380 26026 4399 22024 19934 1975 15152 15912 6813 32014 5847 25893
89 76
20828 21479 16461 25010 24999 19995 3955 5245 21150 7306 7277 3399 26158 8503 15640 5678 23835 4411 18449 8891 28552 28769 15908 23265 16966 10881 7801 22966 25820 26269 20861 7150 9306 28605 22161 23068 16094 20362 8309 19113 17379 30381 19571 1936 11597 3813 8267 5087 32053 21226 31458 15597 27764 2053 9129 21340 30193 30060 9422 30669 19115 30047 7205 30566 31365 31747 11989 29701 24021 12289 3010 21569 2987 28894 10430 14117 26849 26393 9839 26539 7143 31238 1790 3066 29003 18285 9093 3167 32011
45 20
28173 1178 4834 16202 7573 32180 6578 25264 25891 11746 10231 27762 2686 14028 21270 26087 20670 6978 31050 13723 22986 2313 21894 7166 9112 29541 29968 20175 7460 19051 27353 24390 3885 23299 23711 22276 21682 9151 17857 14267 7984 10847 3045 18845 17048
12 12
25734 17682 21193 12528 8168 11892 24691 4195 5498 21377 29723 29542
64 34
7401 23884 21657 27108 8765 3085 27498 24311 11903 22825 8078 20450 23203 19522 5722 19911 26239 15224 12594 16603 10700 5508 9070 9697 2558 12691 31498 10091 196 16616 2063 3792 32605 15920 20165 18668 15009 30372 28822 31386 11210 2273 14272 24818 20999 30087 12738 31043 191 7571 1156 11471 18085 19069 27204 31817 14720 7185 69 26383 12984 30734 21558 2600
91 14
23651 13052 4229 3549 18077 25045 30074 26082 18922 30745 12257 12331 26349 3652 10681 8085 17172 11688 23467 3924 2691 27108 28371 3795 1220 5670 12111 20302 18475 4640 7048 20273 14346 27339 7235 24368 14746 19166 12646 23843 19364 30477 8075 16551 27890 20994 27206 21877 32121 9244 10038 16256 1603 8938 30158 9425 5150 29798 10209 6435 4359 10737 26351 10045 18516 28434 25137 5139 419 26606 20838 14236 24197 31623 22620 1906 26347 1461 5949 12075 28748 11492 29599 21113 19356 22419 26185 21764 26093 32136 22982
10 1
20691 26028 15772 8151 31370 29353 29185 17105 26430 4946
26 5
24383 7596 260 25581 26260 20854 30896 1061 8377 5948 23480 13477 13334 9245 29283 24007 26948 3671 23141 29138 511 7831 19525 32043 1001 27139
51 21
29444 259 1560 6687 14317 16083 17878 24339 11737 1482 23035 19868 5201 29799 2741 1911 24749 24352 11238 2884 11090 6891 708 32754 13483 25737 26928 19178 15848 28821 19160 23803 12665 28752 22539 25096 22345 5929 2655 16243 4283 27919 22277 3400 22629 31095 10983 30249 399 4908 3206
50 46
24794 32662 20313 23568 22104 1622 8106 5951 15032 23729 6694 17621 785 18710 31096 19211 3591 7960 22566 16497 3103 20421 12226 31149 8388 9158 7893 14067 2072 31547 8587 11587 19836 12115 10526 26470 24286 29103 15875 15014 2245 17780 6359 19280 10014 28210 24072 23786 5828 28792

AC output:

Code: Select all

31730 / 22830 / 3272 4144 16256 20385 / 2435 13740 20324 10870 / 27414 4722 11245 10638 / 15417 29839 / 19155 4537 26608 / 21387 25380 / 26684 21840 / 20034 3058 27140 / 29714 / 10883 6590 15014 / 1497 12906 26275 / 1822 12355 2942 28994 / 6212 9137 25481 / 32369 / 4365 25303 3899 10659 / 21639 30466 / 30333 / 4117 20370 7468 / 27286 702 8799 14273 / 16896 27380 / 26026 4399 22024 / 19934 1975 15152 15912 / 6813 32014 / 5847 25893
20828 / 21479 / 16461 / 25010 / 24999 / 19995 / 3955 / 5245 / 21150 / 7306 / 7277 / 3399 / 26158 / 8503 / 15640 / 5678 / 23835 / 4411 / 18449 / 8891 / 28552 / 28769 / 15908 / 23265 / 16966 / 10881 / 7801 / 22966 / 25820 / 26269 / 20861 / 7150 / 9306 / 28605 / 22161 / 23068 / 16094 / 20362 / 8309 19113 / 17379 / 30381 / 19571 / 1936 11597 3813 8267 5087 / 32053 / 21226 / 31458 / 15597 / 27764 2053 / 9129 21340 / 30193 / 30060 / 9422 / 30669 / 19115 / 30047 / 7205 / 30566 / 31365 / 31747 / 11989 / 29701 / 24021 / 12289 / 3010 21569 / 2987 28894 / 10430 14117 / 26849 / 26393 / 9839 / 26539 / 7143 / 31238 / 1790 3066 / 29003 / 18285 9093 3167 / 32011
28173 / 1178 4834 16202 / 7573 32180 / 6578 25264 / 25891 11746 10231 / 27762 2686 14028 / 21270 26087 / 20670 6978 / 31050 13723 / 22986 2313 21894 / 7166 9112 29541 / 29968 / 20175 7460 / 19051 27353 / 24390 3885 / 23299 23711 / 22276 21682 / 9151 17857 / 14267 7984 10847 / 3045 18845 17048
25734 / 17682 / 21193 / 12528 / 8168 / 11892 / 24691 / 4195 / 5498 / 21377 / 29723 / 29542
7401 23884 / 21657 / 27108 / 8765 3085 27498 / 24311 / 11903 22825 / 8078 20450 / 23203 / 19522 / 5722 19911 / 26239 15224 / 12594 16603 10700 / 5508 9070 9697 2558 12691 / 31498 / 10091 196 16616 / 2063 3792 32605 / 15920 20165 / 18668 15009 / 30372 / 28822 / 31386 11210 / 2273 14272 24818 / 20999 / 30087 / 12738 / 31043 / 191 7571 1156 11471 / 18085 19069 / 27204 / 31817 / 14720 7185 / 69 26383 12984 / 30734 / 21558 2600
23651 13052 4229 3549 18077 25045 / 30074 26082 18922 30745 12257 / 12331 26349 3652 10681 8085 17172 11688 23467 / 3924 2691 27108 28371 3795 1220 5670 12111 20302 / 18475 4640 7048 20273 14346 27339 7235 / 24368 14746 19166 12646 23843 19364 / 30477 8075 16551 27890 20994 / 27206 21877 32121 9244 10038 16256 / 1603 8938 30158 9425 5150 29798 10209 6435 4359 10737 / 26351 10045 18516 28434 25137 5139 / 419 26606 20838 14236 24197 31623 / 22620 1906 26347 1461 5949 12075 28748 11492 / 29599 21113 19356 22419 26185 / 21764 26093 32136 22982
20691 26028 15772 8151 31370 29353 29185 17105 26430 4946
24383 7596 260 25581 26260 / 20854 30896 1061 8377 5948 23480 / 13477 13334 9245 29283 24007 / 26948 3671 23141 29138 / 511 7831 19525 32043 1001 27139
29444 259 1560 6687 / 14317 16083 17878 / 24339 11737 / 1482 23035 19868 / 5201 29799 / 2741 1911 24749 / 24352 / 11238 2884 11090 / 6891 708 32754 / 13483 25737 / 26928 19178 / 15848 28821 / 19160 23803 / 12665 28752 / 22539 25096 / 22345 5929 2655 16243 / 4283 27919 / 22277 / 3400 22629 / 31095 10983 / 30249 399 4908 3206
24794 / 32662 / 20313 / 23568 / 22104 / 1622 / 8106 / 5951 / 15032 / 23729 / 6694 / 17621 / 785 / 18710 / 31096 / 19211 / 3591 / 7960 / 22566 / 16497 / 3103 / 20421 / 12226 / 31149 / 8388 / 9158 / 7893 / 14067 / 2072 / 31547 / 8587 / 11587 / 19836 / 12115 / 10526 / 26470 / 24286 / 29103 / 15875 / 15014 / 2245 17780 6359 / 19280 10014 / 28210 / 24072 / 23786 5828 / 28792