Submission #1291429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291429		nishu	Teleporters (IOI08_teleporters)	C++17	0 / 100	1100 ms	128516 KiB

teleporters

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

// Assume segment from 0 to L, with N initial teleporters, M new to add
int main() {
    int N, M, L, dist;
    cin >> N >> M >> L >> dist;
    set<int> endpoints;
    vector<pair<int,int>> teleporters;

    // Read the existing teleporters' endpoints
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        teleporters.push_back({a, b});
        endpoints.insert(a);
        endpoints.insert(b);
    }

    // Track points already marked as teleport endpoints
    set<int> used = endpoints;
    vector<bool> visited(L+1, false);

    // Simulate walk and add new teleporters greedily
    int position = 0;
    int added = 0;
    while (added < M) {
        // Look for the furthest unvisited endpoint at least 'dist' behind
        int tele_end = -1;
        for (int back = position - dist; back >= 0; --back) {
            if (!visited[back] && !used.count(back)) {
                tele_end = back;
                break;
            }
        }
        if (tele_end == -1) break; // No valid unvisited found

        // Place teleporter between current position and tele_end
        teleporters.push_back({position, tele_end});
        used.insert(tele_end);
        used.insert(position);
        visited[tele_end] = true;
        visited[position] = true;
        added++;

        // Move forward for next placement
        // For simplicity, let's assume next position is the next unvisited spot
        for (int i = position+1; i <= L; ++i) {
            if (!visited[i] && !used.count(i)) {
                position = i;
                break;
            }
        }
    }

    // Each added teleporter gives +2 points forcibly
    int base_points = N;  
    int total_points = base_points + 2 * added;
    cout << "Total points: " << total_points << endl;
    cout << "Teleporters placed (existing + new):" << endl;
    for (auto &p : teleporters)
        cout << p.first << " " << p.second << endl;

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5