oj.uz

Submission #675139

# Submission time Handle Problem Language Result Execution time Memory
675139 2022-12-27T02:10:23 Z mousey Table Tennis (info1cup20_tabletennis) C++14
100 / 100
 422 ms 43324 KB 
  //#pragma GCC optimize("Ofast,unroll-loops")
  //#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
  #include <bits/stdc++.h>
  #define int long long
  #define ll long long
  #define vll vector<ll>
  #define vllp vector<pair<ll, ll> >
  #define vi vector <int>
  #define vip vector <pair <int, int> >
  #define db double
  #define ldb long double
  #define pdb pair <double, double> 
  #define YES cout<<"Yes"
  #define NO cout<<"No"
  #define nl cout<<"\n"
  #define vv vector <vector <ll> >
  #define pll pair <ll, ll> 
  #define pi pair <int, int>
  #define pb push_back
  #define f first
  #define s second
  using namespace std;

  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

  const ll mod=1e9+7;
  const ll modx=998244353;
  const double eps=1e-9;
  const ll INF=2e9;
  const ll INFINF=9e18;
  const int N=150000, K=400;
  int n, k, a[N+K+5];
  vi v, ans;
  map <int, int> dem;

  void input()
  {
    cin >> n >> k;
    for(int i = 1; i <= n+k; i++)
    {
      cin >> a[i];
    }
  }

  bool ktra(int sum)
  {
    int l=1, r=n+k;
    int cnt=0;
    while(l<r)
    {
      if(a[l]+a[r]==sum)
      {
        cnt+=2;
        l++;
        r--;
      }
      else if(a[l]+a[r]>sum) r--;
      else l++;
    }
    if(cnt>=n) return true;
    return false;
  }

  void print(int sum)
  {
    int l=1, r=n+k;
    while(l<r)
    {
      if(a[l]+a[r]==sum)
      {
        if((int) ans.size()<n) ans.pb(a[l]), ans.pb(a[r]);
        l++;
        r--;
      }
      else if(a[l]+a[r]>sum) r--;
      else l++;
    }
    sort(ans.begin(), ans.end());
    for(auto i: ans) cout << i << " ";
  }

  void solve()
  {
    if(n+k>=4*k)
    {
      for(int l = 1; l <= min(2*k, n+k); l++)
      {
        for(int r = n+k; r >= max(n-k, 1ll); r--)
        {
          if(l>=r) continue;
          else
          {
            // cout << l << " " << r << "\n";
            dem[a[l]+a[r]]++;
          }
        }
      }
      for(auto i: dem)
      {
        // cout << i.f << " " << i.s << "\n";
        if(i.s<k) continue;
        else
        {
          if(ktra(i.f))
          {
            print(i.f);
            return;
          }
        }
      }
    }
    else
    {
      for(int l = 1; l <= k+1; l++)
      {
        for(int r = n+k; r >= n; r--)
        {
          if(l-1+n+k-r<=k)
          {
            if(ktra(a[l]+a[r]))
            {
              print(a[l]+a[r]);
              return;
            }
          }
          else break;
        }
      }
    }
  }
  signed main() 
  {
  //  auto start_time = chrono::high_resolution_clock::now();
    // #ifdef ONLINE_JUDGE
    //   freopen("f.in", "r", stdin);
    // #endif
    // freopen("f.in", "r", stdin);
    // freopen("kek.out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t=1;
    // cin >> t;
    for(int i = 1; i <= t; i++)
    {
      input();
      solve();
    }
  //    auto end_time = chrono::high_resolution_clock::now();
  //        double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
  //        cout << "\n[ " << duration << " ms ]\n"; 
  }

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 984 KB Output is correct
2 Correct 44 ms 4208 KB Output is correct
3 Correct 58 ms 4236 KB Output is correct
4 Correct 36 ms 4228 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 4244 KB Output is correct
2 Correct 48 ms 4304 KB Output is correct
3 Correct 49 ms 4232 KB Output is correct
4 Correct 44 ms 4232 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 1 ms 232 KB Output is correct
4 Correct 3 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 448 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 45 ms 4312 KB Output is correct
3 Correct 42 ms 4268 KB Output is correct
4 Correct 39 ms 4208 KB Output is correct
5 Correct 37 ms 4260 KB Output is correct
6 Correct 44 ms 4216 KB Output is correct
7 Correct 48 ms 4228 KB Output is correct
8 Correct 36 ms 4296 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 422 ms 41040 KB Output is correct
3 Correct 369 ms 43324 KB Output is correct
4 Correct 260 ms 37900 KB Output is correct
5 Correct 150 ms 13408 KB Output is correct
6 Correct 78 ms 4604 KB Output is correct
7 Correct 262 ms 33484 KB Output is correct
8 Correct 212 ms 36540 KB Output is correct