oj.uz

Submission #476509

# Submission time Handle Problem Language Result Execution time Memory
476509 2021-09-27T12:33:54 Z leaked Table Tennis (info1cup20_tabletennis) C++14
100 / 100
 244 ms 4576 KB 
#include <bits/stdc++.h>

#define m_p make_pair
#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<x)
#define sz(x) (int)x.size()
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<long long,long long> pll;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
auto rng=bind(uniform_int_distribution<int>(1,20),mt19937(time(0)));
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

signed main(){
    fast_ioi;
//    while(1){
    int n,k;
//    n=10;k=1;
    cin>>n>>k;
//    srand(11)
    auto gen=[&](){
        int s=rand()+10000;
//        debug()<<imie(s);
        map<int,int>mp;
        vec<int> b;
        for(int j=0;j<n/2;j++){
            int og=rand();
            while(og>=s || mp[og] ) og=rand();
            b.pb(og);b.pb(s-og);
            mp[og]=1;mp[s-og]=1;
        }
        debug()<<imie(b);
        for(int j=0;j<k;j++){
            int og=rand();
            while(mp[og]) og=rand();
            b.pb(og);
            mp[og]=1;
        }
        sort(all(b));
        debug()<<imie(b);
        cout<<endl;
        return b;
    };
    vec<int>a(n+k);
//    a=gen();
    for(auto &z : a) cin>>z;
//    auto gen=
//    sort(all(a));
//    vec<vec<array<int,3>>>lel(n,vec<array<int,3>>());
//    for(int i=0;i<n;i++){
//        for(int j=-k;j<=k;j++){
//            int nj=(n+k-i-1)+j;
//            if(nj>i && nj<n+k && j<=i){
//                lel[i].pb({j,a[i]+a[nj],i});
//            }
//        }
//    }
    int ok=0;
    for(int i=0;i<=k;i++){
        /// so i deleted i elem
        if(ok) break;
        for(int b=i-k;b<=i;b++){
            int nj=(n+k-i-1)+b;
            if(nj<i || nj>=n+k) continue;
            int nd=a[i]+a[nj];
            int uk=nj;
            vec<int>rla;
            for(int j=i;j<n+k;j++){
                while(uk>j  && a[j]+a[uk]>nd) uk--;
                if(uk==j) break;
                if(sz(rla)+(uk-j+1)<n) break;
//                if(abs(n+k-j-1-uk)>k) break;
//                if(b==0 && j==5){
//                    debug()<<imie(a[j]+a[uk])imie(nd);
//                }
                if(a[j]+a[uk]==nd && abs(n+k-j-1-uk)<=k){
                    rla.pb(a[j]);rla.pb(a[uk]);
                    if(sz(rla)==n) break;
                }
            }
            if(sz(rla)==n){
                sort(all(rla));
                for(auto &z : rla) cout<<z<<' ';
                ok=1;
                break;
            }
        }
    }
    cout<<endl;
//    vec<pii>srts;
//    vec<int>uks(n,0);
//    for(int j=0;j<n*k;j++){

//    }
    assert(ok);
//    }
    return 0;
}
/*
6 1
5447 7526 7703 8705 18716 19718 19895
1582 7087 7911 14379 14703 14703 19265 19265 19589 26057 32386
*/

Compilation message

tabletennis.cpp: In function 'int main()':
tabletennis.cpp:59:10: warning: variable 'gen' set but not used [-Wunused-but-set-variable]
   59 |     auto gen=[&](){
      |          ^~~

Subtask #1
11.0 / 11.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 876 KB Output is correct
2 Correct 41 ms 4292 KB Output is correct
3 Correct 41 ms 3772 KB Output is correct
4 Correct 39 ms 3796 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 4216 KB Output is correct
2 Correct 39 ms 4284 KB Output is correct
3 Correct 37 ms 4180 KB Output is correct
4 Correct 44 ms 3808 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 320 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 40 ms 4288 KB Output is correct
3 Correct 38 ms 3888 KB Output is correct
4 Correct 37 ms 3716 KB Output is correct
5 Correct 37 ms 3772 KB Output is correct
6 Correct 45 ms 3784 KB Output is correct
7 Correct 36 ms 3776 KB Output is correct
8 Correct 38 ms 3796 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 92 ms 4244 KB Output is correct
3 Correct 37 ms 4472 KB Output is correct
4 Correct 65 ms 4480 KB Output is correct
5 Correct 67 ms 4396 KB Output is correct
6 Correct 244 ms 4576 KB Output is correct
7 Correct 95 ms 4528 KB Output is correct
8 Correct 40 ms 4416 KB Output is correct