GCJ Kickstart Round D Problem A: Solution and sample data

A-small-attempt-3.out

Case #1: 13
Case #2: IMPOSSIBLE
Case #3: 2
Case #4: 386239
Case #5: IMPOSSIBLE
Case #6: IMPOSSIBLE
Case #7: IMPOSSIBLE
Case #8: 84609596512776
Case #9: 0
Case #10: 1155268877829
Case #11: 20023013179934
Case #12: 2520838
Case #13: 99733480146404
Case #14: IMPOSSIBLE
Case #15: 45973119056116
Case #16: 211645185874122
Case #17: IMPOSSIBLE
Case #18: 792826072095
Case #19: 95726086748067
Case #20: IMPOSSIBLE
Case #21: 7739889990419
Case #22: 112277118248099
Case #23: 70787864034221
Case #24: 12533343727692
Case #25: IMPOSSIBLE
Case #26: IMPOSSIBLE
Case #27: 71277740924071
Case #28: IMPOSSIBLE
Case #29: 410687439623
Case #30: IMPOSSIBLE
Case #31: IMPOSSIBLE
Case #32: 10513052276368
Case #33: 60439981515766
Case #34: IMPOSSIBLE
Case #35: 21744329065990
Case #36: 64822339446537
Case #37: IMPOSSIBLE
Case #38: 942448
Case #39: IMPOSSIBLE
Case #40: IMPOSSIBLE
Case #41: IMPOSSIBLE
Case #42: IMPOSSIBLE
Case #43: 2000010
Case #44: 343771755415
Case #45: 183521743865768
Case #46: 19567064295348
Case #47: 7457110015180
Case #48: IMPOSSIBLE
Case #49: 1282747473416
Case #50: 39503122214846
Case #51: 3320300097967
Case #52: IMPOSSIBLE
Case #53: 219644959158686
Case #54: 855898255690
Case #55: IMPOSSIBLE
Case #56: IMPOSSIBLE
Case #57: 1319293
Case #58: 70375880302833
Case #59: IMPOSSIBLE
Case #60: IMPOSSIBLE
Case #61: IMPOSSIBLE
Case #62: 47932945200844
Case #63: 1
Case #64: 161256316130495
Case #65: 100885235593197
Case #66: 181728692226084
Case #67: 183377919343722
Case #68: 75100890847076
Case #69: 40393772379714
Case #70: 73711039428710
Case #71: IMPOSSIBLE
Case #72: IMPOSSIBLE
Case #73: IMPOSSIBLE
Case #74: 55787364673374
Case #75: IMPOSSIBLE
Case #76: 2500035
Case #77: 3100005
Case #78: 25218212965045
Case #79: 7822421306925
Case #80: IMPOSSIBLE
Case #81: IMPOSSIBLE
Case #82: 923585474144
Case #83: 499999999500000
Case #84: IMPOSSIBLE
Case #85: 210874718944330
Case #86: IMPOSSIBLE
Case #87: 18283365188347
Case #88: 3889016209007
Case #89: 48604366656979
Case #90: IMPOSSIBLE
Case #91: 194532195231313
Case #92: 125000
Case #93: 122605223747166
Case #94: 175657328953276
Case #95: IMPOSSIBLE
Case #96: 2500000
Case #97: IMPOSSIBLE
Case #98: 7073416659942
Case #99: IMPOSSIBLE
Case #100: 498684683144

A-small-attempt3.in

100
6 1 1000000000000000
1 1 1 1 0 100 0
6 1 -100
1 1 1 1 0 100 0
2 2 1000000000000000
1 1 0 0 0 1000000000 0
500000 31657 510464
7 2 443572333 891162075 667011199 11 0
255036 124346 -753943938319303
660851040 300729738 91363401 8377580 846524407 99233223 0
293127 213960 -490048322569219
38720034 853607815 993321048 218063489 501885066 749664819 0
2 0 1000000000000000
1 1 0 0 0 1000000000 0
337394 152608 884925220218519
972339224 965051021 968101770 822170879 817240397 554218720 0
500000 500000 1000000000000000
0 0 0 0 0 1000000000 0
125050 5125 766086306038588
975922421 32272472 950391829 555226605 602730750 219584427 0
222874 212789 96205529478698
262181913 652293581 749651974 620305999 954030197 179400287 0
500000 249825 3606849
2 2 252979951 274856338 668733065 11 0
328310 192239 1000000000000000
223147540 350877096 673424645 602148450 959133091 608042357 0
96610 23405 -747752017948894
848362841 31773156 746507122 89111779 781824183 760243721 0
373778 145728 486969394323317
824567785 142010000 586105977 371725758 34717110 315562001 0
500000 500000 1000000000000000
733993375 513548043 870122968 277910966 474522113 847144207 0
167226 153426 -169361817942495
634544920 785207104 953592758 452533702 865716097 456419834 0
8226 7846 457882916916336
834682044 699446414 274249897 207440995 320787649 192640187 0
230445 105017 552239376535646
733367725 206368112 149661712 550039526 353602416 908654227 0
135307 91875 -482200620087528
168736251 914716302 578450133 891234255 387192859 839093437 0
328310 133139 65355209189041
890477179 484081614 732354219 6443255 200093997 57990439 0
266166 190003 642984791170091
469843927 967338529 390348063 240965798 554900576 842221237 0
261897 261897 1000000000000000
702043494 193850717 833709412 382885503 594188396 540077987 0
151857 145585 964980200698474
518967410 977231169 485116161 750237664 524513525 165174231 0
225749 91581 -384197781376211
743568728 976474501 669225530 896425723 997621336 143037189 0
500000 0 511119440468704
794735167 794735167 0 0 794735167 1000000000 0
272472 272472 1000000000000000
824582302 568035185 371615858 264974081 299470778 522677967 0
397766 212736 -775392416799479
117798843 672957349 975475865 441124346 443945302 441586671 0
19532 2761 420765888327106
892413751 934980225 286547950 615495329 126783638 142735469 0
409161 230874 -878375356782915
657037280 978671257 900193172 418095908 251493737 560670731 0
183128 80498 -988169850839689
806867755 96780798 478414835 185487774 60190754 211506545 0
500000 500000 1000000000000000
446334072 675715881 191484228 373475205 370410405 42075863 0
500000 172428 1000000000000000
758412212 537731940 126811623 633054018 848908835 350039641 0
423417 15065 -831868687102976
219864499 13733312 991700554 705357166 981995239 437382609 0
66263 51369 844922816835511
108991471 512931072 38675416 402047301 880725218 657841078 0
500000 289270 167597788485118
27825980 467571322 890261075 919852262 96000841 259580317 0
328310 328310 -561631667952923
48916928 480622786 214915234 508990996 103535513 707975035 0
500000 85676 2567839
0 6 964587394 280299817 874690146 11 0
463125 346977 -994073086281792
306495804 656437690 591142535 208766296 164476044 536243949 0
204949 93632 -728792820975619
729415296 688771507 340622523 101307302 96156036 688122169 0
500000 0 1000000000000000
1 1 0 1 0 1000000000 0
359015 66187 -242346444663742
506889179 526134023 77916096 627266058 659364831 512282307 0
500000 224435 2306226
6 10 663178166 882155801 574105013 11 0
125678 125678 1000000000000000
735067261 101168051 650536559 760141540 908200533 5444867 0
500000 418629 1000000000000000
997833531 4726045 22125707 884447548 893871919 734125681 0
500000 29114 1000000000000000
879950591 363110167 805437312 529268942 557759415 662571567 0
500000 8414 1000000000000000
30042215 956032108 38957106 157721918 654655874 864822429 0
212 31 -657880532722635
691524642 554060765 948018812 564167840 322462070 457259855 0
280116 167724 874625700857020
75698349 321655756 966358282 145973931 784342832 9155327 0
158810 44030 196064758844854
500650391 920916408 896755601 226698637 393660726 896352855 0
120411 36917 136118007260972
377697282 556526257 979779330 632391953 976703241 90124105 0
500000 0 -919553614140562
403566673 403566673 0 0 403566673 1000000000 0
500000 500000 780547294710532
860551390 758013298 950030736 536704293 110237366 878728977 0
29745 1144 776121649388304
473877263 505946272 285623033 126873222 41028872 712641845 0
404879 211217 -247652727923534
351742674 547413217 137427100 371999188 164738293 821615665 0
500000 500000 -566841849906524
116589247 851994173 266651351 62410164 404232429 614738253 0
500000 119929 3445555
2 4 567246777 423686090 250804516 11 0
186622 186622 1000000000000000
161965355 855515293 766665990 398528874 416505225 754346809 0
262651 118784 -839056750931552
286075233 751588890 375117782 933889989 201914999 169832693 0
500000 99439 -42734262131944
190142436 374614067 244546648 679779267 889216818 930730045 0
2542 1836 -379866596752965
41399264 435963996 171479449 643984622 915018508 157024959 0
217661 201070 578507047436202
912800169 239757150 50583294 642715911 402337549 440335925 0
2 1 1000000000000000
1 1 0 0 0 1000000000 0
401519 327156 653354307257655
662212013 481620650 862719420 611990104 721266751 802598721 0
404879 310585 1000000000000000
584100502 877271672 91408855 653648801 892209971 498660541 0
401518 197398 290759751329299
34479117 645093603 914198837 815635686 747380685 920462673 0
500000 500000 1000000000000000
555188721 321356787 803193731 776920539 25265204 733777767 0
500000 500000 75100890847968
740305546 503227036 243930030 4793383 815869728 417722165 0
417799 342385 40393772380190
847486130 746443135 470145518 64830169 367872672 751580197 0
278883 194372 121253649179212
407382799 393241904 427674940 449405575 916948137 527460437 0
323400 0 522024231215367
537375377 537375377 0 0 537375377 1000000000 0
500000 0 -315302127813611
211233625 211233625 0 0 211233625 1000000000 0
328294 193052 -115406019820823
525466683 772531291 490861266 960616994 195073844 438090079 0
146055 146055 214046229990660
793484940 306834927 304666950 236049261 901454565 763358745 0
436144 0 -651762756379534
207097521 207097521 0 0 207097521 1000000000 0
500000 304280 4564617
3 9 21220987 267089861 640684082 11 0
500000 478948 3692063
7 9 442462782 325986122 57979353 11 0
158810 98880 1000000000000000
990054550 209932453 913302912 797332355 385289678 317911927 0
146055 10341 1000000000000000
814813007 29356967 692257246 282135867 929307284 740021889 0
158810 158810 -496837880337427
801036976 522177802 731852563 562599460 274185451 306965199 0
500000 0 559493622368066
238795121 238795121 0 0 238795121 1000000000 0
99902 90949 220078649571824
504043356 21807719 238489119 710586211 315924095 18431829 0
500000 500000 1000000000000000
999999999 999999999 0 0 999999999 1000000000 0
275398 231604 -261790381237789
461234292 187454434 384713023 8800782 412312002 479811635 0
500000 500000 1000000000000000
314146198 740114077 290210228 738215455 458312526 844032947 0
500000 494891 -85409967799318
852941750 322691147 287868920 134355014 63689494 653804915 0
196106 149940 18283365195954
354230979 189023582 414486552 354374174 452949531 583425499 0
500000 7393 199881218585852
31114094 664803459 279743039 631915052 297637400 513303319 0
394709 48855 205665775601322
499625650 426612196 830817505 577076806 136774503 988681117 0
401773 0 173959840226524
204945491 204945491 0 0 204945491 1000000000 0
434878 429658 659319492523153
17806150 121611904 485876219 269986919 335574117 895323525 0
500000 125000 125000
1 0 0 1 0 2 0
404879 404879 629545772947715
375389471 451496082 229005933 635519746 475390386 604792243 0
500000 500000 980765723975054
541722718 289984329 952387606 924292490 674332314 703235849 0
196331 184836 -784789364359882
618425149 440582675 480552993 429289086 290064019 378130593 0
500000 341145 4105680
3 0 869985567 782512950 992071695 11 0
215731 131337 -392683926797175
310097308 110649803 752133798 715444610 270462191 506890739 0
146055 82117 461984884646180
395088110 857093700 738843277 616311244 934401864 96673303 0
236283 0 190814131057683
52810941 52810941 0 0 52810941 1000000000 0
5974 1230 584741708856885
267123510 692798133 810103729 799054922 450443980 390387295 0

solution.cpp

#define T_ long long  
#define fuck(s_) {cout<<s_<<endl;return 0;} 
#define printarr(a_,x_) rep(i_,x_)cout<<a_[i_]<<" ";cout<<endl; 
#define printarr0(a_,x_) rep0(i_,x_)cout<<a_[i_]<<" ";cout<<endl; 
#define printarr2(a_,x_,y_) rep(i_,x_){rep(j_,y_)cout<<a_[i_][j_]<<' ';cout<<endl;} 
#define printarr20(a_,x_,y_) rep0(i_,x_){rep0(j_,y_)cout<<a[i_][j_]<<' ';cout<<endl;} 
#define rep2o(a_,b_,n_) rep(a_,n_) re(b_,a_+1,n_) 
#define rep20o(a_,b_,n_) rep0(a_,n_) re0(b_,a_+1,n_) 
#define rep2(a_,b_,p_,q_) rep(a_,p_) rep(b_,q_)
#define rep20(a_,b_,p_,q_) rep0(a_,p_) rep0(b_,q_) 
#define rrep2(a_,b_,p_,q_) rrep(a_,p_) rrep(b_,q_)
#define rrep20(a_,b_,p_,q_) rrep0(a_,p_) rrep0(b_,q_)
#define rep3(a_,b_,c_,p_,q_,r_) rep(a_,p_) rep(b_,q_) rep(c_,r_)
#define rep30(a_,b_,c_,p_,q_,r_) rep0(a_,p_) rep0(b_,q_) rep0(c_,r_)
#define rrep3(a_,b_,c_,p_,q_,r_) rrep(a_,p_) rrep(b_,q_) rrep(c_,r_)
#define rrep30(a_,b_,c_,p_,q_,r_) rrep0(a_,p_) rrep0(b_,q_) rrep0(c_,r_)
#define rep(a_,x_) re(a_,1,x_) 
#define rep0(a_,x_) re0(a_,0,x_) 
#define rrep(a_,x_) rre(a_,x_,1) 
#define rrep0(a_,x_) rre(a_,x_-1,0) 
#define re(a_,s_,t_) for(T_ a_=s_;a_<=t_;++a_) 
#define re0(a_,s_,t_) for(T_ a_=s_;a_<t_;++a_) 
#define rre(a_,s_,t_) for(T_ a_=s_;a_>=t_;--a_)
#define rre0(a_,s_,t_) for(T_ a_=s_;a_>t_;--a_)
#define repit(a_,c_) for(__typeof__(a_.begin()) c_=a_.begin();c_!=a_.end();++c_) 
#define nosync std::ios::sync_with_stdio(false);std::cin.tie(0);ios_base::sync_with_stdio(0) 
#define DE false
#define de(s_) if(DE){s_ } 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <numeric>
#include <bitset>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <ctime>
#include <stack>
#include <queue>
#include <cassert>
#include <climits>
#pragma GCC optimize("O2")
using namespace std;
#define endl '\n'
const int dx4[] = {-1, 0, 1, 0};
const int dy4[] = {0, 1, 0, -1};  
const long long modb=1000000007;  
const long inf=0x3f3f3f3f;      
const double oo=1e15;           
const double eps=1e-8;          
const double pi=acos(-1.0);     
template<typename T> void clr(T* a_,int n_=0,size_t s_=-1) {if (s_==-1) s_=sizeof(a_); memset(a_,n_,sizeof(a_[0])*s_); }  
template<typename T> T sqr(T a_) { return a_*a_; }  
template<typename T> T cub(T a_) { return a_*a_*a_; }  
inline T_ mf(T_ n_) {return ((n_<0)?n_+(modb<<2):n_)%modb; }  
template<typename T>T max(T a_,T b_,T c_) { return max(a_,max(b_,c_)); } 
template<typename T>T min(T a_,T b_,T c_) { return min(a_,min(b_,c_)); } 
inline int dbcmp(double a_, double b_) { return (fabs(a_-b_)<eps)?0:(a_<b_?-1:1); } 
inline double dbdiv(T_ a_, T_ b_) { return static_cast<double>(a_) / b_; } 
inline double angle(double x_, double y_) { if (x_==0.0) return y_>0?pi/2:3*pi/2; else { double t_=atan2(y_,x_); return (t_<0.0?t_+pi:t_) + y_<0?pi:0.0; }} 
/******************************************************************************************/


using LL = long long;
// fast method, return LONG_LONG_MIN for impossible
LL calc1(LL n, LL o, LL d, LL x1, LL x2, LL a, LL b, LL c, LL m, LL l)
{
    vector<LL> v(n);
    v[0] = x1; v[1] = x2;
    for (int i=2; i<n; ++i)
    {
        v[i] = (a * v[i-1] + b * v[i-2] + c) % m;
    }
    for (auto &num: v)
        num += l;
    de(cout << "v: " << endl;)
    de(printarr0(v, n);)
    vector<int> odd;
    odd.push_back((v[0] + (1LL << 32)) % 2 == 1);
    for (int i=1; i<n; ++i)
        odd.push_back(odd.back() + (v[i] + (1LL << 32)) % 2);
    de(cout << "odd " << endl;)
    de(printarr0(odd, n);)
    vector<LL> s;
    LL ans = LONG_LONG_MIN;
    partial_sum(v.begin(), v.end(), back_inserter(s));
    int cur = 0;
    multiset<LL> ps;
    for (int i=0; i<n; ++i)
    {
        int ed = upper_bound(odd.begin() + i, odd.end(), (i ? odd[i-1] : 0) + o) - odd.begin();
        de(cout << "i=" << i << " ed=" << ed << endl;)
        cur = max(cur, i);
        for (int j=cur; j<ed; ++j)
        {
            ps.insert(s[j]);
        }
        cur = ed;
        LL max_val = (i ? s[i-1] : 0) + d;
        auto it = ps.upper_bound(max_val);
        if (it != ps.begin()) {
            de(cout << " best = " << *prev(it) - (i ? s[i-1] : 0) << endl;)
            ans = max(ans, *prev(it) - (i ? s[i-1] : 0LL));
            assert(*prev(it) - (i ? s[i-1] : 0LL) <= d);
        }
        if (ps.find(s[i]) != ps.end()) ps.erase(ps.find(s[i]));
    }
    return ans;
}

// simple method
LL calc2(LL n, LL o, LL d, LL x1, LL x2, LL a, LL b, LL c, LL m, LL l) {
    vector<LL> v(n);
    v[0] = x1; v[1] = x2;
    for (int i=2; i<n; ++i)
    {
        v[i] = (a * v[i-1] + b * v[i-2] + c) % m;
    }
    for (auto &num: v)
        num += l;
    de(cout << "v'=" << endl;
    printarr0(v, n);)
    LL ans = LONG_LONG_MIN;
    for (int i=0; i<n; ++i)
    {
        int oddcnt = 0;
        LL s = 0;
        for (int j=i; j<n; ++j)
        {
            if ((v[j] + (1LL << 32)) % 2 == 1) ++ oddcnt;
            if (oddcnt > o) break;
            s += v[j];
            if (s <= d)
                ans = max(ans, s);
        }
    }
    return ans;
}

int main()
{
    int T;
    cin >> T;
    rep(t, T)
    {
        LL n,o,d;
        LL x1, x2, a, b, c, m, l;
        cin >> n >> o >> d;
        cin >> x1 >> x2 >> a >> b >> c >> m >> l;
        //n = 50;
        //o = rand() % 8;
        //d = 20;
        //x1 = 0; x2 = 3;
        //a = rand() % 5151; b = rand() % 541515; c = rand() % 15151; m = rand() % 30 + 1; l = rand() % 15 - 8;
        LL ans = calc1(n, o, d, x1, x2, a, b, c, m, l);
        //LL ans2 = calc2(n, o, d, x1, x2, a, b, c, m, l);
        //if (ans != ans2)
        //{
            //cout << "inpu date: " << endl;
            //cout << n << " " << o << " " << d << endl << x1 << " " << x2 << " " << a << " " << b << " " << c << " " << m << " " << l << " ";
            //cout << endl;
            //cout << ans << " | " << ans2 << endl;
            //terminate();
        //}
        cout << "Case #" << t << ": ";
        if (ans > LONG_LONG_MIN)
            cout << ans << endl;
        else
            cout << "IMPOSSIBLE" << endl;
    }
}