# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1046049 | Zicrus | Teleporters (IOI08_teleporters) | C++17 | 1069 ms | 65536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m;
vector<ll> a;
ll simulate(vector<ll> &a) {
ll res = 0;
ll i = 0;
while (i < a.size()) {
i = a[i];
i++;
res++;
}
return res;
}
int main() {
cin >> n >> m;
vector<pair<ll, ll>> tp;
for (int i = 0; i < n; i++) {
ll x, y;
cin >> x >> y;
tp.push_back({x, y});
tp.push_back({y, x});
}
sort(tp.begin(), tp.end());
unordered_map<ll, ll> ids;
for (int i = 0; i < 2*n; i++) {
ids[tp[i].first] = i;
}
a = vector<ll>(2*n);
for (int i = 0; i < 2*n; i++) {
a[i] = ids[tp[i].second];
}
ll mx = simulate(a);
while (m--) {
vector<ll> mxA = a;
mxA.push_back(mxA.size()+1);
mxA.push_back(mxA.size()-1);
mx = simulate(mxA);
for (int i = 0; i < a.size(); i++) {
if (a[i] < i) continue;
vector<ll> nw;
for (int j = 0; j < a.size(); j++) {
if (j == i) {
nw.push_back(i+2);
nw.push_back(a[i]+2);
nw.push_back(i);
continue;
}
if (a[j] == i) nw.push_back(i+1);
else nw.push_back(a[j] > i ? a[j]+2 : a[j]);
}
ll val = simulate(nw);
if (val > mx) {
mx = val;
mxA = nw;
}
}
a = mxA;
}
cout << mx;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |