Submission #1021068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021068		anton	Wombats (IOI13_wombats)	C++17	76 / 100	20053 ms	86420 KiB

wombats

#include "wombats.h"
#include<bits/stdc++.h>

using namespace std;

const int MAX_C= 200;
const int MAX_R = 5000;
const int INF= 1e9;
const int BLOCK_SZ = 50;
const int BLOCK_NB = 101;
struct Step{
    vector<vector<int>> tr;

    Step(){};
    Step(int nbC){
        tr.resize(nbC, vector<int> (nbC, INF));
        for(int i = 0; i<nbC; i++){
            tr[i][i] = 0;
        }
    }

    Step(int nbC, vector<int> lr, vector<int> d){

        assert(lr.size() == nbC-1);
        assert(d.size() == nbC);

        tr.resize(nbC, vector<int> (nbC, 0));
        vector<int> prefCost(nbC);
        for(int iC = 0; iC<nbC-1; iC++){
            prefCost[iC+1] = prefCost[iC] + lr[iC];
        }
        for(int beginC = 0; beginC<nbC; beginC++){
            for(int endC = 0; endC<nbC; endC++){
                if(beginC<=endC){
                    tr[beginC][endC] = prefCost[endC] - prefCost[beginC] + d[endC];
                }
                else{
                    tr[beginC][endC] = prefCost[beginC] - prefCost[endC] + d[endC];

                }
            }
        }
    }

    void display(){
        /*for(int i = 0; i<tr.size(); i++){
            for(auto e: tr[i]){
                cout<<e<<" ";
            }
            cout<<endl;
        }*/
    }
};


int nbC;


void mergeBegin(Step &l, Step &r, Step&res, int Begin, int lMid, int rMid, int lEnd, int rEnd){

    if(rEnd<lEnd){
        return;
    }
    int splitEnd = (lEnd+rEnd)/2;
    int minC= 1e9;
    int minMid = (lMid+rMid)/2;
    for(int iMid = lMid; iMid<=rMid; iMid++){
        if(l.tr[Begin][iMid] + r.tr[iMid][splitEnd] < minC){
            minMid= iMid;
            minC = l.tr[Begin][iMid] + r.tr[iMid][splitEnd];
        }
    }

    res.tr[Begin][splitEnd] = minC;

    mergeBegin(l, r, res, Begin, lMid, minMid, lEnd, splitEnd-1);
    mergeBegin(l, r, res, Begin, minMid, rMid, splitEnd+1, rEnd);

}

Step merge(Step& a, Step b){
    
    Step res(nbC);
    for(int iBegin = 0; iBegin<nbC; iBegin++){
        mergeBegin(a, b, res, iBegin, 0, nbC-1, 0, nbC-1);
    }
    return res;
}

struct Tree{
    int sz = 1;
    vector<Step> tr;
    Tree(){};
    Tree(int l){
        while(sz<l){
            sz*=2;
        }
        tr.resize(2*sz, Step(nbC));
    }

    void upd(int i){
        for(i/=2; i>=1; i/=2){
            //cerr<<i<<endl;
            tr[i] = merge(tr[i*2], tr[i*2+1]);
            tr[i].display();
        }
    }
    void set(int id, Step v){
        tr[id+sz] = v;
        upd(id+sz);
    }
};

Tree tr;
Step steps[BLOCK_NB];
vector<int> lr[MAX_R], d[MAX_R];
Step total;
int nbR;

void recalc_block(int i){
    steps[i] = Step(nbC);
    for(int iR = i*BLOCK_SZ; iR<min((i+1)*BLOCK_SZ, nbR); iR++){
        steps[i] = merge(steps[i], Step(nbC, lr[iR], d[iR]));
    }
    tr.set(i, steps[i]);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    nbC = C;
    nbR = R;
    tr =Tree(BLOCK_NB);
    for(int iR = 0; iR<R; iR++){
        lr[iR].resize(C-1);
        d[iR].resize(C);
        for(int i = 0; i<C-1; i++){
            lr[iR][i] = H[iR][i];
        }
        if(iR<R-1){
            for(int i = 0; i<C; i++){
                d[iR][i] = V[iR][i];
            }
        }
        else{
            for(int i = 0; i<C; i++){
                d[iR][i] = 0;
            }
        }

        //steps.push_back(Step(C, lr[iR], d[iR]));
        //steps.back().display();
    }
    for(int i = 0; i<=(nbR)/BLOCK_SZ; i++){
        recalc_block(i);
    }

}

void changeH(int P, int Q, int W) {
    lr[P][Q] = W;
    recalc_block(P/BLOCK_SZ);
}

void changeV(int P, int Q, int W) {
    d[P][Q] = W;
    recalc_block(P/BLOCK_SZ);
}

int escape(int V1, int V2) {
    return tr.tr[1].tr[V1][V2];
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from wombats.cpp:2:
wombats.cpp: In constructor 'Step::Step(int, std::vector<int>, std::vector<int>)':
wombats.cpp:24:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |         assert(lr.size() == nbC-1);
      |                ~~~~~~~~~~^~~~~~~~
wombats.cpp:25:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |         assert(d.size() == nbC);
      |                ~~~~~~~~~^~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 24