Submission #423985

#TimeUsernameProblemLanguageResultExecution timeMemory
423985pavementTable Tennis (info1cup20_tabletennis)C++17
78 / 100
3041 ms7340 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #endif //#define int long long #define mp make_pair #define mt make_tuple #define pb push_back #define ppb pop_back #define eb emplace_back #define g0(a) get<0>(a) #define g1(a) get<1>(a) #define g2(a) get<2>(a) #define g3(a) get<3>(a) mt19937 rng(28392); typedef double db; typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef tuple<int, int, int> iii; typedef tuple<int, int, int, int> iiii; typedef tree<iii, null_type, greater<iii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; int N, K, A[200005]; vector<ii> ord; map<int, ii> tmp2; main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N >> K; for (int i = 1; i <= N + K; i++) cin >> A[i]; for (int i = 0; i <= K; i++) for (int j = 0; i + j <= K; j++) if (i + 1 < N + K - j && tmp2.find(A[i + 1] + A[N + K - j]) == tmp2.end()) tmp2[A[i + 1] + A[N + K - j]] = mp(i + 1, N + K - j); for (auto [l, r] : tmp2) ord.pb(r); shuffle(ord.begin(), ord.end(), rng); for (auto [l, r] : ord) { int S = A[l] + A[r], cnt = 0, _r = r; for (int k = l; k < _r; k++) { while (k < _r && A[k] + A[_r] > S) _r--; if (A[k] + A[_r] == S) { cnt += 2; if (cnt == N) break; } } if (cnt == N) { int _r = r; vector<int> tmp; for (int k = l; k < _r; k++) { while (k < _r && A[k] + A[_r] > S) _r--; if (A[k] + A[_r] == S) { tmp.pb(A[k]); tmp.pb(A[_r]); if (tmp.size() == N) break; } } sort(tmp.begin(), tmp.end()); for (int k : tmp) cout << k << ' '; cout << '\n'; return 0; } } }

Compilation message (stderr)

tabletennis.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main() {
      | ^~~~
tabletennis.cpp: In function 'int main()':
tabletennis.cpp:61:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |      if (tmp.size() == N) break;
      |          ~~~~~~~~~~~^~~~
#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...