Submission #113360

#	Time	Username	Problem	Language	Result	Execution time	Memory
113360		popovicirobert	Segway (COI19_segway)	C++14	100 / 100	317 ms	34044 KiB

segway

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

struct Fenwick {
    vector <int> aib;
    int n;

    inline void init(int _n) {
        n = _n + 1;
        aib.resize(n + 1);
    }

    inline void update(int pos, int val) {
        pos++;
        for(int i = pos; i <= n; i += lsb(i)) {
            aib[i] += val;
        }
    }

    inline int query(int pos) {
        int ans = 0;
        pos++;
        for(int i = pos; i > 0; i -= lsb(i)) {
            ans += aib[i];
        }
        return ans;
    }

};

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;

    vector < vector <int> > speed(n + 1, vector <int>(3));

    for(i = 1; i <= n; i++) {
        for(j = 0; j < 3; j++) {
            cin >> speed[i][j];
        }
    }

    cin >> m;
    vector <bool> vis(301);

    while(m > 0) {
        m--;

        int x;
        cin >> x;

        vis[x] = 1;
    }

    Fenwick fen; fen.init(300);

    vector < vector <int> > id(50 * 300 + 1);
    vector <int> bonus(n + 1, 0), coord(n + 1, 0), new_coord(n + 1);

    for(i = 1; i <= n; i++) {
        id[0].push_back(i);
        fen.update(0, 1);
    }

    vector <int> sol(n + 1);

    for(i = 0; i <= 50 * 300; i++) {

        int sz = id[i].size();

        for(int j = 0; j < sz; j++) {
            int it = id[i][j];

            if(coord[it] == 300) {
                continue;
            }

            if(bonus[it] == 0 && vis[coord[it]]) {
                bonus[it] = (n - fen.query(coord[it])) % 20;
            }

            if(bonus[it] > 0) {
                bonus[it]--;
                id[i + 1].push_back(it);
            }
            else {
                id[i + speed[it][coord[it] / 100]].push_back(it);
            }

            new_coord[it] = coord[it] + 1;
        }

        for(int j = 0; j < sz; j++) {
            int it = id[i][j];

            if(coord[it] == 300) {
                sol[it] = i;
                continue;
            }

            fen.update(coord[it], -1);
            fen.update(new_coord[it], 1);

            coord[it] = new_coord[it];
        }
    }

    for(i = 1; i <= n; i++) {
        cout << sol[i] << "\n";
    }

    //cin.close();
    //cout.close();
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45