oj.uz

Submission #999846

# Submission time Handle Problem Language Result Execution time Memory
999846 2024-06-16T07:33:21 Z Br3ad Roller Coaster Railroad (IOI16_railroad) C++17
0 / 100
 153 ms 16808 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)

const int N = 2e5 + 5;
const int M = 1e9 + 7; 
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;

/*
Problem statement:
 - Each node: speed limit(s_i), exit speed(t_i)
 - Edge: Track length(x)

Edge Weight: max(t_cur - s_next, 0)
 
Subtask 3:
 - At node i, for all s_next >= t_cur, choose min/max(t_next)

Subtask 4:
 - 
*/

// Subtask 3
ll int plan_roller_coaster(vector<int> s, vector<int> t){
    multiset<pair<int, int>> node; // <speed_limit, exit_speed>
    for(int i = 0; i < s.size(); i++){
        node.insert(MP(t[i], s[i]));
    }

    pair<int, int> cur = *(--node.end());
    node.erase(node.find(cur));

    while(!node.empty()){
        auto it = node.upper_bound(MP(cur.s, inf));
        if(it == node.begin()) return 1;

        it--;
        cur = *it;
        node.erase(it);
    }

    return 0;
}

// int main(){
    
//     ios::sync_with_stdio(false);
//     cin.tie(NULL);
    
//     // ifstream cin();
//     // ofstream cout();
    
//     int temp;
//     temp = plan_roller_coaster({1, 4, 5, 6}, {7, 3, 8, 6});
//     // temp = plan_roller_coaster({3, 4, 7, 4}, {2, 7, 3, 5});
//     // temp = plan_roller_coaster({5, 100, 100}, {101, 1, 100});
//     cout << temp << endl;
// }

/*
1: (100, 100)
2: (100, 1)
3: (5, 101)

1: (100, 1)
2: (5, 101) //terminate

*/

Compilation message

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 2
2 Correct 0 ms 348 KB n = 2
3 Correct 0 ms 348 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 0 ms 348 KB n = 2
6 Incorrect 0 ms 348 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 2
2 Correct 0 ms 348 KB n = 2
3 Correct 0 ms 348 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 0 ms 348 KB n = 2
6 Incorrect 0 ms 348 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 12952 KB n = 199999
2 Correct 153 ms 12740 KB n = 199991
3 Correct 96 ms 12780 KB n = 199993
4 Correct 96 ms 9812 KB n = 152076
5 Correct 53 ms 6068 KB n = 93249
6 Correct 106 ms 12764 KB n = 199910
7 Correct 118 ms 12756 KB n = 199999
8 Correct 98 ms 12732 KB n = 199997
9 Correct 106 ms 11120 KB n = 171294
10 Correct 76 ms 9044 KB n = 140872
11 Correct 110 ms 15708 KB n = 199886
12 Correct 100 ms 15952 KB n = 199996
13 Correct 98 ms 15700 KB n = 200000
14 Correct 102 ms 15956 KB n = 199998
15 Correct 99 ms 15952 KB n = 200000
16 Correct 106 ms 16208 KB n = 199998
17 Correct 99 ms 16808 KB n = 200000
18 Correct 99 ms 15996 KB n = 190000
19 Correct 83 ms 14908 KB n = 177777
20 Correct 55 ms 8532 KB n = 100000
21 Incorrect 119 ms 16720 KB answer is not correct: 1 instead of 0
22 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 2
2 Correct 0 ms 348 KB n = 2
3 Correct 0 ms 348 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 0 ms 348 KB n = 2
6 Incorrect 0 ms 348 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -