Submission #1046049

#TimeUsernameProblemLanguageResultExecution timeMemory
1046049ZicrusTeleporters (IOI08_teleporters)C++17
55 / 100
1069 ms65536 KiB
#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)

teleporters.cpp: In function 'll simulate(std::vector<long long int>&)':
teleporters.cpp:12:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     while (i < a.size()) {
      |            ~~^~~~~~~~~~
teleporters.cpp: In function 'int main()':
teleporters.cpp:46:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int i = 0; i < a.size(); i++) {
      |                         ~~^~~~~~~~~~
teleporters.cpp:49:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for (int j = 0; j < a.size(); j++) {
      |                             ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...