oj.uz

Submission #999866

# Submission time Handle Problem Language Result Execution time Memory
999866 2024-06-16T07:46:02 Z Br3ad Roller Coaster Railroad (IOI16_railroad) C++17
0 / 100
 163 ms 12956 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;
        it = node.upper_bound(MP(cur.f, 0));
        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({100, 5, 5}, {4, 1, 101});
//     cout << temp << endl;
// }

/*
1: (100, 4)
2: (5, 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 344 KB n = 2
2 Correct 0 ms 344 KB n = 2
3 Correct 0 ms 348 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 1 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 344 KB n = 2
2 Correct 0 ms 344 KB n = 2
3 Correct 0 ms 348 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 1 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 98 ms 12880 KB n = 199999
2 Correct 163 ms 12884 KB n = 199991
3 Correct 96 ms 12944 KB n = 199993
4 Correct 90 ms 9808 KB n = 152076
5 Correct 59 ms 6040 KB n = 93249
6 Correct 116 ms 12744 KB n = 199910
7 Correct 100 ms 12880 KB n = 199999
8 Correct 99 ms 12748 KB n = 199997
9 Correct 150 ms 11348 KB n = 171294
10 Correct 117 ms 9224 KB n = 140872
11 Correct 107 ms 12716 KB n = 199886
12 Correct 121 ms 12880 KB n = 199996
13 Correct 118 ms 12760 KB n = 200000
14 Correct 125 ms 12884 KB n = 199998
15 Correct 111 ms 12756 KB n = 200000
16 Correct 115 ms 12776 KB n = 199998
17 Correct 125 ms 12760 KB n = 200000
18 Correct 131 ms 12116 KB n = 190000
19 Correct 100 ms 11304 KB n = 177777
20 Correct 64 ms 6684 KB n = 100000
21 Incorrect 143 ms 12956 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 344 KB n = 2
2 Correct 0 ms 344 KB n = 2
3 Correct 0 ms 348 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 1 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 -