Submission #1207639

#TimeUsernameProblemLanguageResultExecution timeMemory
1207639lopkusSubway (info1cup19_subway)C++20
100 / 100
5 ms1728 KiB
#include <bits/stdc++.h> #define int long long void solve() { int k; std::cin >> k; int h = 0; std::vector<std::pair<int,int>> ans; ans.push_back({1, 0}); // h * (h - 1) / 2 int node = 2; int last = 0; for(int i = 1; ; i++) { if(i * (i - 1) / 2 <= k) { last = i; } else { break; } } for(int i = 2; i <= last; i++) { ans.push_back({i, i - 1}); } node = last + 1; k -= last * (last - 1) / 2; while(k > 0) { int lst = 0; for(int i = 1; ; i++) { if(i * (i - 1) / 2 <= k) { lst = i; } else { break; } } if(k <= last) { ans.push_back({node, k}); break; } int prv = 1; for(int i = 1; i < lst; i++) { ans.push_back({node, prv}); prv = node++; } k -= lst * (lst - 1) / 2; } std::cout << ans.size() << "\n"; for(auto [x, y] : ans) { x -= 1; y -= 1; std::cout << x << " " << y << "\n"; } } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t = 1; //std::cin >> t; while (t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...