oj.uz

Submission #1020973

# Submission time Handle Problem Language Result Execution time Memory
1020973 2024-07-12T12:23:27 Z anton Wombats (IOI13_wombats) C++17
18 / 100
 1260 ms 11060 KB 
#include "wombats.h"
#include<bits/stdc++.h>

using namespace std;

const int MAX_C= 200;
const int MAX_R = 5000;
struct Step{
    vector<vector<int>> tr;

    Step(){};
    Step(int nbC){
        tr.resize(nbC, vector<int> (nbC, 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));
        vector<int> prefCost(nbC+1);
        for(int iC = 0; iC<nbC; 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;
        }*/
    }
};

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){
    int l = a.tr.size();
    Step res(l);
    for(int iBegin = 0; iBegin<l; iBegin++){
        mergeBegin(a, b, res, iBegin, 0, l-1, 0, l-1);
    }
    return res;
}


vector<Step> steps;
vector<int> lr[MAX_R], d[MAX_R];
int nbC;
Step total;

void recalc_all(){
    total = Step(steps[0]);
    for(int i = 1; i<steps.size(); i++){
        total.display();
        steps[i].display();
        total = merge(total, steps[i]);
        total.display();
    }
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    nbC = C;
    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();
    }
    recalc_all();

}

void changeH(int P, int Q, int W) {
    lr[P][Q] = W;
    steps[P] = Step(nbC, lr[P], d[P]);
    recalc_all();
}

void changeV(int P, int Q, int W) {
    d[P][Q] = W;
    steps[P] = Step(nbC, lr[P], d[P]);
    recalc_all();
}

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

Compilation message

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:18:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |         assert(lr.size() == nbC-1);
      |                ~~~~~~~~~~^~~~~~~~
wombats.cpp:19:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |         assert(d.size() == nbC);
      |                ~~~~~~~~~^~~~~~
wombats.cpp: In function 'void recalc_all()':
wombats.cpp:88:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Step>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i = 1; i<steps.size(); i++){
      |                    ~^~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 9564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1148 ms 7312 KB Output is correct
2 Correct 1169 ms 7236 KB Output is correct
3 Correct 1252 ms 7344 KB Output is correct
4 Correct 1260 ms 7260 KB Output is correct
5 Correct 1188 ms 7256 KB Output is correct
6 Runtime error 1 ms 860 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 9624 KB Output is correct
2 Correct 249 ms 9564 KB Output is correct
3 Correct 249 ms 9560 KB Output is correct
4 Correct 262 ms 10796 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1161 ms 7292 KB Output is correct
2 Correct 1111 ms 7260 KB Output is correct
3 Correct 1169 ms 7512 KB Output is correct
4 Correct 1193 ms 7344 KB Output is correct
5 Correct 1157 ms 7256 KB Output is correct
6 Correct 246 ms 9564 KB Output is correct
7 Correct 235 ms 9620 KB Output is correct
8 Correct 259 ms 9560 KB Output is correct
9 Correct 262 ms 10840 KB Output is correct
10 Runtime error 5 ms 9560 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1191 ms 7260 KB Output is correct
2 Correct 1104 ms 7260 KB Output is correct
3 Correct 1218 ms 7344 KB Output is correct
4 Correct 1158 ms 7344 KB Output is correct
5 Correct 1134 ms 7260 KB Output is correct
6 Correct 287 ms 9564 KB Output is correct
7 Correct 233 ms 9564 KB Output is correct
8 Correct 251 ms 9628 KB Output is correct
9 Correct 272 ms 11060 KB Output is correct
10 Runtime error 7 ms 9564 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -