Submission #834341

#	Time	Username	Problem	Language	Result	Execution time	Memory
834341		unnick	Arcade (NOI20_arcade)	C++14	65 / 100	1041 ms	16404 KiB

Arcade

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n,m;
    cin >> n >> m;
    std::vector<int> times(m);
    std::vector<int> positions(m);

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

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

    std::vector<int> idxes(m);
    std::iota(idxes.begin(), idxes.end(), 0);

    // for (int i = 0; i < m; i++) {
    //     idxes.push_back(i);
    // }

    std::sort(idxes.begin(), idxes.end(), [times, positions](int ia, int ib){
        int sa = times[ia] + positions[ia];
        int sb = times[ib] + positions[ib];
        return sa == sb ? times[ia] < times[ib] : sa < sb;
    });

    std::vector<int> asdf(m);
    for (int i = 0; i < m; i++) {
        asdf[i] = positions[i]-times[i];
    }

    std::vector<int> frontier;
    int num_arms = 0;

    for (int idx : idxes) {
        int sel = num_arms;
        for (int st = 1<<20; st >>= 1; st > 0) {
            int idx2 = sel-st;
            if (idx2 < 0) continue;
            if (asdf[idx] > frontier[idx2]) continue;
            sel -= st;
        }

        // for (int i = 0; i < num_arms; i++) {
        //     int idx2 = frontier[i];
        //     // check if we can reach the button
        //     if (positions[idx]-times[idx] > positions[idx2]-times[idx2]) continue;
        //     // use the "least useful" hand
        //     if (selected_score < positions[idx2]-times[idx2]) continue;
        //     // cout << idx2 << " is better\n";
        //     selected_score = positions[idx2]-times[idx2];
        //     selected_idx = i;
        // }
        if (sel == num_arms) {
            // cout << "pushed" << "\n";
            frontier.push_back(asdf[idx]);
            num_arms++;
        } else {
            // cout << "replaced " << sel << "\n";
            frontier[sel] = asdf[idx];
        }
        // cout << "frontier: ";
        // for (int i : frontier) {
        //     cout << i << " ";
        // }
        // cout << "\n";
    }

    cout << num_arms << '\n';
}

Compilation message (stderr)

Arcade.cpp: In function 'int main()':
Arcade.cpp:46:43: warning: for increment expression has no effect [-Wunused-value]
   46 |         for (int st = 1<<20; st >>= 1; st > 0) {
      |                                        ~~~^~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 14 / 14
• Subtask 6: 0 / 20
• Subtask 7: 0 / 15