oj.uz

Submission #233347

# Submission time Handle Problem Language Result Execution time Memory
233347 2020-05-20T09:36:12 Z VEGAnn Segway (COI19_segway) C++14
40 / 100
 1000 ms 2780 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
const int N = 20100;
const int M = 310;
const int md = int(1e9) + 7;
const int TIM = 20000;
vector<array<int, 3> > vc;
vector<int> events[M][2];
int a[N][3], n, tim[N], m, ans[N], mem[N], fast[N], OST[N], OSS[TIM];
bool loc[M];

bool cmp(int _x, int _y){
    return tim[_x] < tim[_y];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
        vc.PB({i, 0, 0});
    }

    for (int i = 0; i < TIM; i++)
        OSS[i] = i % 100;

    OST[0] = 0;

    for (int i = 1; i <= n; i++)
        OST[i] = i % 20;

    cin >> m;

    for (int i = 0; i < m; i++){
        int x; cin >> x;
        loc[x] = 1;
    }

    int tim = 0;

    while (sz(vc)){
        for (array<int, 3> cr : vc) {
            if (cr[1] == 300)
                ans[cr[0]] = tim;
            else events[cr[1]][cr[2]].PB(cr[0]);
        }

        vc.clear();

        int kol = n;

        for (int i = 0; i < 300; i++)
        for (int tp = 0; tp < 2; tp++){
            if (sz(events[i][tp]) == 0) continue;

            kol -= sz(events[i][tp]);
            int ost = min(300 - i, OST[kol]);

            if (tp == 0 && loc[i] && ost > 0){

                for (int cr : events[i][tp]){
                    int speed = a[cr][0];

                    if (i > 99)
                        speed = a[cr][1];
                    if (i > 199)
                        speed = a[cr][2];

                    if (fast[cr] > 0){
                        vc.PB({cr, i + 1, 0});
                        mem[cr] = tim + 1;
                        fast[cr]--;
                    } else {
                        fast[cr] = ost - 1;
                        mem[cr] = tim + 1;

                        vc.PB({cr, i + 1, 0});

                        if (OSS[(i + 1)] == 0)
                            mem[cr] = tim + 1;
                    }
                }
            } else {
                for (int cr : events[i][tp]){
                    int speed = a[cr][0];

                    if (i > 99)
                        speed = a[cr][1];
                    if (i > 199)
                        speed = a[cr][2];

                    if (fast[cr] > 0){
                        vc.PB({cr, i + 1, 0});
                        mem[cr] = tim + 1;
                        fast[cr]--;
                    } else {
                        if (mem[cr] % speed == (tim + 1) % speed) {
                            vc.PB({cr, i + 1, 0});

                            if (OSS[(i + 1)] == 0)
                                mem[cr] = tim + 1;
                        } else vc.PB({cr, i, 1});
                    }
                }
            }

            events[i][tp].clear();
        }

        tim++;
    }

    for (int i = 0; i < n; i++)
        cout << ans[i] << '\n';

    return 0;
}

Compilation message

segway.cpp: In function 'int main()':
segway.cpp:71:25: warning: variable 'speed' set but not used [-Wunused-but-set-variable]
                     int speed = a[cr][0];
                         ^~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 512 KB Output is correct
2 Correct 38 ms 512 KB Output is correct
3 Correct 101 ms 632 KB Output is correct
4 Correct 326 ms 1144 KB Output is correct
5 Execution timed out 1091 ms 2780 KB Time limit exceeded

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 512 KB Output is correct
2 Correct 14 ms 512 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 17 ms 512 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 18 ms 512 KB Output is correct
8 Correct 21 ms 512 KB Output is correct
9 Correct 20 ms 512 KB Output is correct
10 Correct 32 ms 512 KB Output is correct
11 Correct 9 ms 512 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 512 KB Output is correct
2 Correct 38 ms 512 KB Output is correct
3 Correct 101 ms 632 KB Output is correct
4 Correct 326 ms 1144 KB Output is correct
5 Execution timed out 1091 ms 2780 KB Time limit exceeded