Description

This problem will help you understand how to use std::map.

http://en.cppreference.com/w/cpp/container/map

Notice, this time, first and last is [first, last].

目前有五個測資，第三筆測資不算，答題測資看另外四筆

Input

The input consist of series of command. Each commands is insert, range output or range erase.

insert: inserts a string (cmd) with the key (key) to map. If the key has already existed, insert the cmd at the begining of string (the string which the key belongs).

For example,

insert 0 "abc"

insert 1 "def"

the map should contain "abc", "def".

insert 0 "xyz"

the map should contain "xyzabc", "def".

range output: outputs the string from key (first) to key (last). Output a space character (' ') after printing an element.

range erase: erase the string from key (first) to key (last).

operator<<: outputs all strings in map. From the smallest key to biggest key. Output a space character (' ') after printing an element.

Output

Complete insert, output, erase and operator<<.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

This problem will help you understand how to use std::set and comparator.

e.g., std::set<std::vector<int>>

http://en.cppreference.com/w/cpp/container/set

Input

How to compare the integer sequence (calculate the key of an integer sequence):

• get the length of integer sequence (size)
• key value=[first element]*(size)+[second element]*(size-1)+[third element]*(size-2)+...+[last element]*1
• compare the key value. Small key value is smaller.
• if the length of a integer sequence is 0, the key value is 0.
• e.g., the key of an integer sequence "3 9 -1 3 -6" is 48 (3*5+9*4+(-1)*3+3*2+(-6)*1)

The input consist of series of command. Each commands is insert, range_out or output.

​insert: inserts an integer sequence (each value is greater than -6 and smaller than 11, stop reading from cin when value is 0). If the key has already existed, then

• output "exist\n"
• erase the integer sequence from set
• reverse the integer sequence (from input)
• insert the reversed integer sequence

For example,

insert 3 9 -1 3 -6 0

The set should contain 3 9 -1 3 -6.

insert 9 -2 6 6 0

The set should contain 6 6 -2 9.

range_out: outputs all integer sequences from the integer sequence (first key) to the integer sequence (second key) of set (including the second key). First key and second key are read from input (each value is greater than -6 and smaller than 11, stop reading from cin when value is 0).

For example,

insert 2 -5 -5 0

insert 3 9 -1 3 -6 0

insert 7 6 1 2 0

insert 10 10 10 2 0

range_out -5 0 10 9 2 0

It should output

3 9 -1 3 -6

7 6 1 2

For example,

insert 2 -5 -5 0

insert 3 9 -1 3 -6 0

insert 7 6 1 2 0

insert 10 10 10 2 0

range_out -5 0 10 10 10 0

It should output

3 9 -1 3 -6

7 6 1 2

output: outputs all integer sequences from the smallest key to the biggest key of set. Output a space character (' ') after printing an integer. Output a newline character ('\n') after printing all elements of a key.

Output

Complete insert, range output and output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Niflheimr is playing Minecraft recently. He occupies a lot of towns, and there are many diamonds inside some of those towns.

Whenever he runs out of diamond, he has to figure out the nearest town with diamonds from his current location.

Doing this task every time waste a lot of time. He asks you to help him for the calculation. For every town, find the shortest distance to get diamonds from a nearby town which has diamonds. If the town itself has diamonds, the distance would be 0.

Hint: Use BFS (Breadth First Search) and std::queue.

If you are not familiar with BFS, you should take a look at the following article:

http://alrightchiu.github.io/SecondRound/graph-breadth-first-searchbfsguang-du-you-xian-sou-xun.html

[IMPORTANT] For those almost run out of time, maybe this note can help you figure out BFS and solve this problem faster!

You are provided with the following code:

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

// G[i] is the neighbor towns of town i
vector<int> diamondTowns;
vector<int> G[100005];
int Dist[100005];

struct node {
    int id;
    int dist;
    node(int id, int l) {
        this->id = id;
        this->dist = l;
    }
};

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for (int i = 0; i < K; i++) {
        int x;
        cin >> x;
        diamondTowns.push_back(x);
    }
    fill(Dist, Dist+100005, -1);

    queue<node> Q;

    // [TODO] complete the task!

    // Output
    for (int i = 1; i <= N; i++) {
        cout << Dist[i] << '\n';
    }
    return 0;
}

 You may take it as reference. You are not required to use this code, though.

Input

First line of input contains three integer N, M, K, denoting the number of towns, the amount of roads between towns and the number of towns which has diamond.

All the towns are numbered from 1 to N.

For the next M lines, each of them contains two integer a, b, meaning there is a road between a and b. All the roads are bidirectional, and the length of these roads are all 1.

The last line of input contains K distinct integers, denoting the towns which has diamonds.

It is guaranteed that:

• 1 <= K <= N <= 10⁵
• 1 <= M <= min(10⁶, N*(N+1)/2)
• All the towns can reach each other, i.e. the graph is connected.

Output

Output consists of N lines.

For i-th line, output the shortest distance Niflheimr has to travel from town i to get a diamond.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In a university, the student council has introduced a new voting system to decide on various proposals. Each student can cast a vote with a specific numeric value representing the priority they place on a proposal. The council needs a system to manage these votes efficiently.

Your goal is to help the student council by developing a program that manages the voting numbers. The system should be able to add votes, remove votes, and quickly determine the highest priority vote still active.

Operations:

1. Add x: Adds a vote with value x to the system. If x is already present, it will be added again.
2. Remove x: Removes one instance of the vote with value x from the system. If x is not present, no action is taken.
3. Max: Returns the highest vote value currently in the system. If no votes are present, print "No votes recorded".
4. Min:  Returns the lowest vote value currently in the system. If no votes are present, print "No votes recorded".

Hint

How to get the minimum value in the std::multiset or std::set

std::multiset<int> st = {1, 2, 3};
auto it = st.begin();
std::cout << "minimum = " << *it;

How about get the maximum value in the std::multiset or std::set

std::multiset<int> st = {1, 2, 3};
auto it = prev(st.end());
std::cout << "maximum = " << *it;

set::end() returns an iterator pointing to the next element of the last one in the container (Like a dummy node in linked-list). Since it does not refer to a valid element, it cannot use '*' to dereferenced end() function.

std::next() & std::prev() are useful function to move through iterators.

When using multiset, please notice the following difference of multiset::erase().

std::multiset<int> st = {1, 1, 1};
st.erase(1); // delete all three "1"
st.erase(st.find(1)); // delete one "1"

Remember: if the set is empty or the iterator you are using point to a invalid element, using '*', 'std::next()', 'set:erase()' or other function might lead to Runtime Error.

Input

• The first line contains an integer Q, the number of operations.
• The next Q lines describe the operations. "Add" and "Remove" operation are formatted as a string followed by an integer x.

​Constraints:

• 1 ≤ Q ≤ 200000
• −10⁹ ≤ x ≤ 10⁹

Output

• For each "Max" and "Min" operation, output the result in a new line.
• If no votes are present, print "No votes recorded".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given \(N\) integers \(a_1 \dots a_N\) and \(M\) queries.
In each query, you will be given one integer \(x\), please output an integer in \(a\) which is closest to \(x\).
If there are more than one such integer, please output the smaller one.

ps. We suggest you use std::set to do this problem :)

Input

The first line contains two integers \(N, M\).
The second line contains \(N\) integers \(a_1, a_2 \dots a_N\)
Each of the next \(M\) lines contains an integer \(x\).

\(N \quad M\)
\(a_1 \quad a_2 \dots a_N\)
\(x_1\)
\(\vdots\)
\(x_M\)

Constraints

• \(1 \le N, M \le 10^5\)
  
• \(0 \le a_i, x_i \le 10^9\)

Output

Please output the answer of each query.

Sample Input  Download

Sample Output  Download

Tags

Discuss