Submission #1368373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1368373		po_rag526	Table Tennis (info1cup20_tabletennis)	C++17	0 / 100	8 ms	1860 KiB

tabletennis

#include<bits/stdc++.h>
using namespace std;

void FREOPEN(const string &prob) {
    freopen((prob + ".in").c_str(), "r", stdin);
    freopen((prob + ".out").c_str(), "w", stdout);
}

#define debug(c) cout << #c << " = " << c << endl
#define debugc() cout << "PASS" << endl

#define nl "\n"
#define fl flush
#define int long long

#define ll long long
#define str string
#define ld long double

#define Pb push_back
#define pB pop_back
#define ub upper_bound
#define lb lower_bound
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define ft first
#define sc second

const ll mod = 1e9+7;
const ld pi = 3.1415926535;

void solve() {
    int n,k; cin >> n >> k;
    
    vector<int> a(n+k+1);
    for(int i=1;i<=n+k;i++) cin >> a[i];

    //sudah pasti n element awal itu barisan aritmetika
    //karena jika di sort, a[1] + a[n] = a[2] + a[n-1] = a[3] + a[n-2] = ...
    //di mana jika untuk setiap 1 <= i <= n, nilai a[i] + a[n-i+1] sama semua, ini berarti barisan ini adalah barisan aritmetika
    //maka soal ini sama saja dengan memilih k element dihapus sehingga sisa element nya adalah barisan aritmetika

    //element pertama pasti ada di range 1 <= i <= k+1
    //element kedua pasti ada di range i+1 <= j <= i + (k - (i-1)) + 1 atau i+1 <= j <= k + 2 
    //dst...

    //ada n-1 kali transisi kita, atau a[i+1] = a[i]+b
    
    if(n == 2) {
        //kalo n == 2, element yang apapun yang dipilih adalah barisan aritmetika
        cout << a[1] << " " << a[2] << nl;
    } else if(n-1 > k) {
        
        //jika n-1 > k, artinya pasti ada element x dan x+b di index i dan i+1 yang tidak dihapus
    
        auto check = [&](int x, int y, int l, int b) -> bool {
            vector<int> res = {a[x], a[y]};

            for(;l <= n+k; l++) 
                if(a[l] - res.back() == b) res.Pb(a[l]);

            if(res.size() < n) return 0;
            
            for(int i=0;i<min(n, (int)res.size());i++) cout << res[i] << " ";
            cout << nl;
            return 1;

        };

        for(int i=1;i<min(n+k-1, 2*k+1);i++) {
            int b = a[i+1] - a[i];

            if(check(i, i+1, i+2, b)) return;
        }
    } else {
        //jika tidak, lakukan dp biasa saja

        int m = n+k;
        vector<vector<int>> dp(m+1, vector<int>(m+1, 2));
        //dp[i][j] -> panjang barisan aritmetika jika 2 indeks terakhir di indeks i dan j (i < j)

        for (int mid=2;mid<m;mid++) {
            int l = mid - 1, r = mid + 1;

            while (l >= 1 && r <= m) {
                int sum = a[l] + a[r], tar = 2 * a[mid];
                if (sum == tar) {
                    dp[mid][r] = dp[l][mid] + 1;
                    
                    if (dp[mid][r] >= n) {
                        int b = a[r] - a[mid], x = a[mid];
                        
                        deque<int> dq; 
                        dq.Pb(a[mid]); dq.Pb(a[r]);
                        
                        while(dq.size() < n) {
                            x -= b;
                            dq.push_front(x);
                        }
                        
                        for(auto &i : dq) cout << i << " ";
                        cout << nl;
                        return;
                    }
                    
                    l--; r++;
                } else if (sum < tar) r++; 
                else l--;
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0); 
    // FREOPEN("");
    
    int T = 1; //cin >> T;
    while(T--) solve();
}

Compilation message (stderr)

tabletennis.cpp: In function 'void FREOPEN(const std::string&)':
tabletennis.cpp:5:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 |     freopen((prob + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tabletennis.cpp:6:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |     freopen((prob + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 9
• Subtask 3: 0 / 14
• Subtask 4: 0 / 15
• Subtask 5: 0 / 9
• Subtask 6: 0 / 14
• Subtask 7: 0 / 15
• Subtask 8: 0 / 13