oj.uz

답안 #888308

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
888308 2023-12-16T23:11:14 Z raul2008487 Table Tennis (info1cup20_tabletennis) C++17
100 / 100
 62 ms 7780 KB 
/// R
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define in insert
#define mpr make_pair
#define vl vector<ll>
//#define endl '\n'
using namespace std;
const int sz = 2e5+5;
const ll inf = 1000000000000000;
//tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> rbt;a
/*struct DSU{
    vector<ll> e;
    void init(ll n){
        e.assign(n+1, -1);
    }
    ll base(ll x){
        if(e[x] < 0){
            return x;
        }
        return e[x] = base(e[x]);
    }
    bool unite(ll a, ll b){
        a = base(a);
        b = base(b);
        if(a == b){return false;}
        if(e[a] > e[b]){
            swap(a, b);
        }
        e[a] += e[b];
        e[b] = a;
        return true;
    }
};*/
ll n, k, m;
vl d, v(sz);
void print(ll bg, ll ed){
    ll pl = bg, pr = ed, l = bg + 1, r = ed - 1, cnt = 1;
    vl res;
    res.pb(v[bg]);res.pb(v[ed]);
    while(l < r){
        ll s2 = (v[pr] - v[r]);
        ll s1 = (v[l] - v[pl]);
        if(s1 == s2){
            cnt++;
            pl = l;
            pr = r;
            //cout << v[l] << ' ' << v[r] << endl;
            res.pb(v[l]);
            res.pb(v[r]);
            l++;r--;
        }
        else if(s1 > s2){
            r--;
        }
        else{
            l++;
        }
    }
    sort(all(res));
    for(int i=0;i<n;i++){
        cout << res[i] << ' ';
    }cout << endl;
}
bool check(ll bg, ll ed, ll pos){
    ll pl = bg, pr = ed, l = bg + 1, r = ed - 1, cnt = 1;
    if(l > r){return true;}
    while(l < r && pos <= k){
        ll s2 = (v[pr] - v[r]);
        ll s1 = (v[l] - v[pl]);
        if(s1 == s2){
            cnt++;
            pl = l;
            pr = r;
            l++;r--;
        }
        else if(s1 > s2){
            r--;
            pos++;
        }
        else{
            l++;
            pos++;
        }
    }
    cnt *= 2;
    return (cnt >= n);
}
void solve(){
    ll i, j, bg, ed, pt, w1, w2, cnt, l, r, cc;
    cin>>n>>k;
    m = n + k;
    for(i=0;i<m;i++){
        cin>>v[i];
    }
    for(i=1;i<m;i++){
        d.pb(v[i] - v[i-1]);
    }
    for(i=0;i<=k;i++){
        for(j=0;j<=k-i;j++){
            if(check(i, m - j - 1, i + j)){
                print(i, m - j - 1);
                return ;
            }
        }
    }
    //assert(0);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}
/*
6 3
1 2 3 6 7 9 10 12 14


1 3 6 7 10 12
*/

Compilation message

tabletennis.cpp: In function 'void solve()':
tabletennis.cpp:94:14: warning: unused variable 'bg' [-Wunused-variable]
   94 |     ll i, j, bg, ed, pt, w1, w2, cnt, l, r, cc;
      |              ^~
tabletennis.cpp:94:18: warning: unused variable 'ed' [-Wunused-variable]
   94 |     ll i, j, bg, ed, pt, w1, w2, cnt, l, r, cc;
      |                  ^~
tabletennis.cpp:94:22: warning: unused variable 'pt' [-Wunused-variable]
   94 |     ll i, j, bg, ed, pt, w1, w2, cnt, l, r, cc;
      |                      ^~
tabletennis.cpp:94:26: warning: unused variable 'w1' [-Wunused-variable]
   94 |     ll i, j, bg, ed, pt, w1, w2, cnt, l, r, cc;
      |                          ^~
tabletennis.cpp:94:30: warning: unused variable 'w2' [-Wunused-variable]
   94 |     ll i, j, bg, ed, pt, w1, w2, cnt, l, r, cc;
      |                              ^~
tabletennis.cpp:94:34: warning: unused variable 'cnt' [-Wunused-variable]
   94 |     ll i, j, bg, ed, pt, w1, w2, cnt, l, r, cc;
      |                                  ^~~
tabletennis.cpp:94:39: warning: unused variable 'l' [-Wunused-variable]
   94 |     ll i, j, bg, ed, pt, w1, w2, cnt, l, r, cc;
      |                                       ^
tabletennis.cpp:94:42: warning: unused variable 'r' [-Wunused-variable]
   94 |     ll i, j, bg, ed, pt, w1, w2, cnt, l, r, cc;
      |                                          ^
tabletennis.cpp:94:45: warning: unused variable 'cc' [-Wunused-variable]
   94 |     ll i, j, bg, ed, pt, w1, w2, cnt, l, r, cc;
      |                                             ^~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2652 KB Output is correct
2 Correct 29 ms 6100 KB Output is correct
3 Correct 26 ms 6100 KB Output is correct
4 Correct 26 ms 6096 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 6276 KB Output is correct
2 Correct 26 ms 6096 KB Output is correct
3 Correct 26 ms 6100 KB Output is correct
4 Correct 26 ms 6244 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1880 KB Output is correct

Subtask #7
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 26 ms 6168 KB Output is correct
3 Correct 27 ms 7648 KB Output is correct
4 Correct 27 ms 7632 KB Output is correct
5 Correct 29 ms 7532 KB Output is correct
6 Correct 27 ms 7632 KB Output is correct
7 Correct 28 ms 7780 KB Output is correct
8 Correct 26 ms 7632 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 50 ms 6164 KB Output is correct
3 Correct 27 ms 7636 KB Output is correct
4 Correct 41 ms 7636 KB Output is correct
5 Correct 27 ms 7532 KB Output is correct
6 Correct 30 ms 7636 KB Output is correct
7 Correct 62 ms 7728 KB Output is correct
8 Correct 27 ms 7636 KB Output is correct