oj.uz

Submission #791280

# Submission time Handle Problem Language Result Execution time Memory
791280 2023-07-23T21:55:51 Z HD1 Table Tennis (info1cup20_tabletennis) C++14
100 / 100
 323 ms 49720 KB 
//we are all lost trying to be someone.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define sz(x) ll(x.size())
#define reve(x) reverse(x.begin(),x.end())
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
const ll MAX=3*(1e6+100);
const ll mod=1e9+7;
const ll inf=1e18+7;
ll A[MAX], s[MAX];
vector<ll >c;
bool nice=false;
ll n, k;
map<ll,ll>M;
void solve(ll sum){
    ll j=n+k-1;
    for(ll i = 0; i < n+k and A[i] < sum/2; i++){
        while(j-1 >= 0 and A[j-1] >= sum-A[i]){
            j--;
        }
        if( j > i and A[j] == sum-A[i]){
            c.push_back(A[j]);
            c.push_back(A[i]);
            if(sz(c) >= n){
                nice=true;
                return;
            }
        }
    }
    return;
}
int main(){
    cin>>n>>k;
    for(ll i = 0; i < n + k; i++){
        cin>>A[i];
    }
    sort(A, A+n+k);
    if(n+k<=4*k){
            for(ll i = 0; i < n+k; i++){
                    for(ll j = 0; j < n+k; j++){
                            if(i!=j){
                                    ll sum=A[i]+A[j];
                                    solve(sum);
                                    if(nice)break;
                                    c.clear();
                            }
                    }
                    if(nice)break;
            }
            sort(c.begin(),c.end());
            for(ll i = 0; i < sz(c); i++){
                cout<<c[i]<<" ";
            }
            cout<<'\n';
            return 0;
    }
    ll cont = 0;
    ll aux = k + 1;
    if(n+k>=4*k) aux = 2*k;
    for(ll i = 0; i < aux; i++){
            for(ll j = n+k-1; j > n+k-1-aux ; j--){
                s[cont] = A[i] + A[j];
                M[s[cont]]++;
                cont++;
            }
    }
    if(n+k >= 4*k){
        cont=0;
        for(auto it: M){
            if(it.ss>=k){
                s[cont]=it.ff;
                cont++;
            }
        }
    }
    for(ll i=0; i<cont; i++){
        solve(s[i]);
        if(nice)break;
        c.clear();
    }
    sort(c.begin(),c.end());
    for(ll i = 0; i < sz(c); i++){
        cout<<c[i]<<" ";
    }
    cout<<'\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 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1076 KB Output is correct
2 Correct 69 ms 5688 KB Output is correct
3 Correct 73 ms 5592 KB Output is correct
4 Correct 60 ms 5640 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 5588 KB Output is correct
2 Correct 57 ms 5708 KB Output is correct
3 Correct 60 ms 5692 KB Output is correct
4 Correct 58 ms 5676 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 7 ms 212 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 3 ms 212 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 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #6
14.0 / 14.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 312 KB Output is correct
2 Correct 58 ms 5836 KB Output is correct
3 Correct 58 ms 5736 KB Output is correct
4 Correct 64 ms 5652 KB Output is correct
5 Correct 58 ms 5712 KB Output is correct
6 Correct 58 ms 5788 KB Output is correct
7 Correct 58 ms 5688 KB Output is correct
8 Correct 59 ms 5736 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 323 ms 47468 KB Output is correct
3 Correct 319 ms 49720 KB Output is correct
4 Correct 227 ms 44296 KB Output is correct
5 Correct 146 ms 19880 KB Output is correct
6 Correct 81 ms 11028 KB Output is correct
7 Correct 226 ms 39996 KB Output is correct
8 Correct 212 ms 43048 KB Output is correct