Submission #752058

#TimeUsernameProblemLanguageResultExecution timeMemory
752058StickfishTable Tennis (info1cup20_tabletennis)C++17
72 / 100
99 ms6556 KiB
#include <iostream> #include <algorithm> #include <set> #include <map> #include <cassert> #include <vector> using namespace std; using ll = long long; const int MAXN = 157000; int get_bestval(vector<int> a, int k) { int n = a.size(); map<int, int> mp; for (int i = 0; i < n; ++i) { int ctr = n - i - 1; for (int t = -k; t <= k; ++t) { if (ctr + t <= i || ctr + t >= n) continue; int val = a[i] + a[ctr + t]; ++mp[val]; } } int mxval = 0; int mxcnt = 0; for (auto [val, cnt] : mp) { if (mxcnt < cnt) { mxval = val; mxcnt = cnt; } } return mxval; } vector<int> get_withsum(vector<int> a, int sm) { int n = a.size(); int j = n - 1; vector<int> ans; for (int i = 0; i < n; ++i) { while (j > i && a[i] + a[j] > sm) --j; if (a[i] + a[j] == sm) { ans.push_back(a[i]); ans.push_back(a[j]); } } return ans; } void solve_slow(vector<int> a, int n, int k) { int mxval = get_bestval(a, k); vector<int> ans = get_withsum(a, mxval); while (ans.size() > n) ans.pop_back(); sort(ans.begin(), ans.end()); for (int i = 0; i < n; ++i) { cout << ans[i] << ' '; } cout << '\n'; } const ll MOD = 1000000007; ll pw(ll a, ll m) { if (!m) return 1; a %= MOD; if (m % 2) return a * pw(a, m - 1) % MOD; return pw(a * a, m / 2); } void solve_smallk(vector<int> a, int n, int k) { int m = n + k; vector<int> na; for (int i = 0; i < 2 * k; ++i) na.push_back(a[i]); for (int i = m - 2 * k; i < m; ++i) na.push_back(a[i]); int mxval = get_bestval(na, k); vector<int> ans = get_withsum(a, mxval); while (ans.size() > n) ans.pop_back(); sort(ans.begin(), ans.end()); for (int i = 0; i < n; ++i) { cout << ans[i] << ' '; } cout << '\n'; return; vector<int> dif(m - 1); for (int i = 0; i + 1 < n + k; ++i) { dif[i] = a[i + 1] - a[i]; } vector<ll> phash_(m); vector<ll> rhash_(m); vector<ll>::iterator phash = phash_.begin() + 1; vector<ll>::iterator rhash = rhash_.begin() + 1; for (int i = 0; i + 1 < m; ++i) { phash[i] = (phash[i - 1] + pw(101, i) * dif[i]) % MOD; rhash[i] = (rhash[i - 1] + pw(101, i) * dif[m - 2 - i]) % MOD; } int lb = 1, ub = n / 2 + 1; while (ub - lb > 1) { int mb = (lb + ub) / 2; set<ll> hashes; for (int i = 0; i + mb < m - 1; ++i) { ll hsh = (phash[i + mb] - phash[i - 1]) / pw(101, MOD - 1 - i); hashes.insert(hsh); //hashes.push_back( } } } signed main() { int n, k; cin >> n >> k; vector<int> a(n + k); for (int i = 0; i < n + k; ++i) { cin >> a[i]; } if (n * k <= 1000000) { solve_slow(a, n, k); return 0; } else { } }

Compilation message (stderr)

tabletennis.cpp: In function 'void solve_slow(std::vector<int>, int, int)':
tabletennis.cpp:53:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |     while (ans.size() > n)
      |            ~~~~~~~~~~~^~~
tabletennis.cpp: In function 'void solve_smallk(std::vector<int>, int, int)':
tabletennis.cpp:82:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |     while (ans.size() > n)
      |            ~~~~~~~~~~~^~~
#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...