Submission #706799

#	Time	Username	Problem	Language	Result	Execution time	Memory
706799		Nursik	Segway (COI19_segway)	C++17	100 / 100	43 ms	1396 KiB

segway

#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <random>

using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
 
const ll maxn = 1e5 + 1, maxm = 1e3 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blcok = 400, p2 = 31;
const ld eps = 1e-9;

int n, m;
int is[maxm], sped[maxn], pref[maxn], pos[maxn];
ll ans[maxn], a[3][maxn];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i){
        for (int j = 0; j < 3; ++j){
            cin >> a[j][i];
        }
        pos[i] = 0;
    }
    cin >> m;
    for (int x, i = 1; i <= m; ++i){
        cin >> x;
        is[x] = 1;
    }
    for (int i = 0; i < 300; ++i){
        for (int j = 0; j <= 15000; ++j){
            pref[j] = 0;
        }
        ll mx = 0;
        for (int j = 1; j <= n; ++j){
            pref[ans[j]] += 1;
            mx = max(mx, ans[j]);
        }
        for (int j = 1; j <= mx; ++j){
            pref[j] += pref[j - 1];
        }
       /* if (i == 189){
          //  cout <<
            for (int j = 1; j <= n; ++j){
                cout << ans[j] << " " << pref[ans[j] - 1] << '\n';
            }
            exit(0);
        }
        */
        int type = 0;
        if (i >= 100 && i < 200){
            type = 1;
        }
        else if (i >= 200){
            type = 2;
        }
        for (int j = 1; j <= n; ++j){
            if (sped[j] && pos[j] < 300){
                pos[j] += 1;
                ans[j] += 1;
                sped[j] -= 1;
            }
            else if (pos[j] < 300){
                int val = (ans[j] - 1 >= 0 ? pref[ans[j] - 1] : 0);
                val %= 20;
                if (is[i] > 0){
                    sped[j] = val;
                }
                if (sped[j] > 0){
                   // cout << "ok\n";
                    sped[j] -= 1;
                    pos[j] += 1;
                    ans[j] += 1;
                }
                else{
                    ans[j] += a[type][j];
                }
            }
        }
        /*if (i == 100){
            cout << ans[1];
            cout << a[type][1] << '\n';
            exit(0);
        }*/
    }
    for (int i = 1; i <= n; ++i){
        cout << ans[i] << '\n';
    }
}
/*
*/

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