# | Problem | Pass Rate (passed user / total user) |
---|---|---|
12558 | I2P(II) Chen_cpp_cheatsheet |
|
12564 | A lot of sandwiches (mid2) |
|
12565 | Vector Implementation (mid2) |
|
12566 | Endgame (mid2) (bonus) |
|
12567 | Break my heart(mid2) |
|
Description
I/O optimization
If you encounter a TLE, you may try to use this optimization for C++ I/O functions:
std::ios_base::sync_with_stdio(false);
cin.tie(0);
And replace all std::endl
with '\n'
.
Do note that you must not use any of C I/O functions such as scanf
, printf
, fgets
if you use this optimization.
<vector>
#include <iostream>
#include <vector>
#include <algorithm> // sort
int main () {
std::vector<int> V;
int x;
while (std::cin >> x) {
V.push_back(x);
}
for (auto t : V) std::cout << " " << t;
std::cout << "\n";
std::sort(V.begin(), V.end());
for (auto t : V) std::cout<<" "<< t;
std::cout << "\n";
}
<queue>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
int main() {
string s;
queue<string> q;
while (cin >> s) {
if (s == "Push") {
cin >> s;
q.push(s);
}
else if (s == "Pop") {
if (q.size()>0)
q.pop();
}
else if (s == "Front") {
if (q.size() == 0)
cout << "empty\n";
else
cout << q.front() << "\n";
}
}
}
<stringstream>
#include <string>
#include <iostream>
#include <sstream> // std::stringstream
int main () {
std::stringstream ss;
ss << "Hello " << 123;
std::string s = ss.str();
std::cout << s << '\n';
}
<set>
#include <iostream>
#include <set>
int main()
{
std::set<int> S = {1, 2, 3, 4};
auto search = S.find(2);
if(search != S.end()) {
std::cout << (*search) << '\n';
}
else {
std::cout << "Not found\n";
}
}
<stack>
#include <stack>
#include <iostream>
int main()
{
std::stack<int> s;
s.push( 3 ); s.push( 6 );
s.push( 18 );
std::cout<<s.size()<<" elements\n";
std::cout<<"Top: "<< s.top()<< "\n";
s.pop();
std::cout<<s.size()<<" elements\n";
}
getline()
#include <string>
#include <iostream>
int main()
{
std::string name;
std::cout << "What is your name? ";
std::getline(std::cin, name);
std::cout << "Hello "<< name<< "\n";
}
<map>
#include <iostream>
#include <string>
#include <map>
#include <utility> // make_pair
int main()
{
std::map<std::string, int> ID;
ID.insert(std::make_pair("Tom", 123));
std::cout << ID["Tom"] << "\n";
}
<string>
#include <iostream>
#include <string>
int main() {
std::string str1, str2, out;
while (std::cin >> str1 >> str2) {
out.clear();
for(auto t : str1) out.push_back(t);
std::cout << out << '\n';
out += str2;
std::cout << out << '\n';
out.pop_back();
std::cout << out << '\n';
for(size_t i = 0; i < out.size(); i++)
std::cout << out[i];
std::cout << '\n';
}
}
Miscellaneous
For more standard library or C++ reference, please refer to this file and rename the downloaded file(12534.cpp
) to reference.zip
, then unzip it. There's a readme inside the zip.
If you have difficulty renaming file, try the following command on terminal (Windows)
move 12534.cpp reference.zip
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Gordon Ramsay: What are you ?
A poor chef: An idiot sandwich.
You are Gordon Ramsay's chief advisor. He's going to judge a lot of sandwiches whether it is an idiot sandwich or not. However, recording the result is too tired for him, so he yells at you for help.
You are given n
sandwiches. Gordon will tell you the label of each sandwich in the following formats:
-
Ramsay <lvl>
: All sandwiches followed with this format are idiot sandwiches. And the numberlvl
is the level of the intelligence of the corresponding idiot sandwich. -
<name>
: All sandwiches withname
not equals to "Ramsay" are masterpiece(in Gordon's opinion, it's a normal sandwich), andname
is its name.
And you're asked to record each sandwich with the following formats:
-
For idiot sandwiches, record
An idiot sandwich with intelligence level <lvl> only.
, wherelvl
is the intelligence level of the sandwich. -
For normal sandwiches, record
<name>. Masterpiece of sandwiches.
, wherename
is the name of the sandwich.
Note that this problem is special judge, you have to implement the functions that marked with TODO
in function.h
.
Input
The first line contains exactly one integer, indicates .
There are lines below. Each line contains one of the sandwich format.
.
for all level of idiot sandwiches.
for all names of normal sandwiches. All letters are 'a' - 'z' or 'A' - 'Z' without any space or newline.
Output
For each sandwich, output its record.
Sample Input Download
Sample Output Download
Partial Judge Code
12564.cppPartial Judge Header
12564.hTags
Discuss
Description
No memes, stories, jokes, or javascript that makes the problem disappears, yay o(* ̄▽ ̄*)o
This problem is partial judge. And you are going to implement a vector by yourself.
Things you need to implement:
-
vector()
: Constructor of our vector.CAPACITY
andSIZE
are initially 0. -
void push_back(T x)
: Same aspush_back
function in STL. Note that ifCAPACITY
equals toSIZE
, you have to double the size ofarr
first, then push element in. -
T & operator [] (const int &x)
: Random access, same as STL. Avector<int> V
should be able to access every element ofarr
by callingV[x]
. -
const T & operator [] (const int &x) const
: Random access for any constant object. -
vector<T> & operator = (const vector<T> &x)
: Implementation of assignment operator=
. Use to copy the content of a vector into another vector by=
, for example:v1=v2
. Note that you must copy the content ofv2.arr
intov1.arr
instead of just copy the pointer ofarr
. -
size_t size() const
: Same assize
function in STL. Return the size of the vector. -
size_t capacity() const
: Same ascapacity
function in STL. Return the total size thatarr
has allocated. -
void reserve(size_t x)
: Same asreserve
function in STL. This function will increase the capacity tox
, which means to extend the size ofarr
to sizex
. Note that ifx
is not greater than the current capacity, the function do nothing. After reserving, all the data that had pushed in should remain the same. -
void clear()
: Same asclear
function in STL. The function resetSIZE
to 0. Note thatCAPACITY
won't change in this function. Also, this function will destruct all the elements.
After implementing these functions, we'll give you several commands:
-
push_back <t1>
: callpush_back(t1)
-
pop_back
: callpop_back()
-
access <t1>
: callv[t1]
-
size
: outputsize()
-
capacity
: outputcapacity()
-
reserve <t1>
: callreserve(t1)
-
clear
: callclear
-
backup
: store the current state of the vector into a temporary storage. -
restore
: load the previous saved vector and replace the current vector.
It is guaranteed that no illegal operation will appear, such as pop_back
while the vector is empty, accessing index that exceeds the size, or restore
without any backup.
Input
The first line contains an integer, indicates the number of commands.
The next lines are all commands that describe above.
The number of commands won't exceed .
The parameter of reserve
will be in range of , and all other parameters will be in range of .
Output
Output when the corresponding commands appears.
Sample Input Download
Sample Output Download
Partial Judge Code
12565.cppPartial Judge Header
12565.hTags
Discuss
Description
episode 1: http://140.114.86.238/problem/12254/
episode 2: http://140.114.86.238/problem/12436/
episode 3: http://140.114.86.238/problem/12522/
After Iron Man grab all the infinity stones from Thanos and set them onto his hand, he now has the ability to decide the destiny of the whole universe...
After snapping, Iron Man's mind is teleported into the deepest layer of the stones. He knows who he have to eliminate, that is, the Thanos army.
Iron Man & Thanos thinking about this problem.
If you click Iron Man, something might happen...
Iron Man's mind is now located in a 2-dimension flat with lives of all creatures. He can eliminate any creature by stepping on it. Most lives are innocent creatures, and Iron Man doesn't want to eliminate them. Those lives he wants to eliminate is only the Thanos army.
As he is now in a spiritual form, he can split himself, search, and eliminate Thanos army in every direction at the same time. He can only walk up, down, left, and right. Diagonal movement such as up-left or down-right is not allowed.
Iron Man wants to know the minimum distance he have to walk in order to eliminate all the Thanos army.
You are given a flat.
Every position may be in the following state:
.
: There's nothing here, you can pass this place without worrying.I
: Here is the initial position you're at. There will be exactly oneI
on the flat.T
: The Thanos army are represented as aT
. You have to eliminate allT
on the flat. To eliminate them, you have to step onto every place with stateT
at least once.C
: All other innocent creatures. You cannot pass by or walk on this place since Iron Man don't want to eliminate innocents.
You're going to find out the minimum furthest distance that you need to walk.
Take sample as an example, the distance is marked below, and those red places is the place where you have to go through.
323C9
C1C98
C0CC7
212C6
CC345
Input
The first line contains two integers and .
There are lines below. Each line contains characters, indicate the state of all positions of the flat initially.
.
Output
Output the minimum distance that Iron Man have to walk in order to eliminate all the Thanos army. If it's impossible, output -1
.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
I have broken many girls' hearts into pieces. But none of them mad at me. None.
~ by anonymous surgeon
You're a surgeon, you need to mend those girls' hearts. Therefore you need a data structure to support some functions.
This question is about maintain a set that contains only integers.
There will be n instructions.
Each instruction will be either:
insert
:
Insert a new element ai into the set. Note that if the element has already in the set, do nothing.
print
:
print all the element in the set in increasing order.
min
:
print the number in the set that is the smallest. If there's no number, do nothing.
range_erase
:
You will have two integer l, r.
You need to erase all the elements ai in the set that l <= ai <= r
sum
: (Different from practice!!)
print the sum of all the elements in the set.
Hint: You can solve this question very fast by using std::set
.
These are some functions you may use in your code:
set.begin()
, set.size()
, set.erase()
, set.lower_bound()
, set.upper_bound()
, set.insert()
, note the return value of set.insert()
. To traverse through your set, you may also need iterator
or type auto
(only in c++11!)
Download the C++ reference.
You will see the file named "12534.cpp" but that's OK.
Just download the file and change the filename extension(副檔名) into "zip" then you can upzip the file and use the reference.
The link is below.
Input
the input will contain several lines.
The first line only contains an integer n
The following are n lines.
Each lines contains a instruction list above.
Note that 0 <= ai, l, r <= 10^9
Range of n:
testcase 1~4: 1 <= n <= 5000
testcase 5: n = 200000
For testcase 5 there's no "print" instruction!
Output
For each print
instruction, print all the number in the set in increasing order.
Each number is separated by a single blank.(No blank at the the end!)
Remember to print \n
at the end of output
For each min
instruction, print the smallest number in the set.
Remember to print \n
at the end of output