Submission #826491

#	Time	Username	Problem	Language	Result	Execution time	Memory
826491		nasir_bashirov	Cryptography (NOI20_crypto)	C++11	0 / 100	1072 ms	212 KiB

Crypto

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

// #define endl '\n'
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define all(x)    x.begin(), x.end()
#define fastio\
    ios_base::sync_with_stdio(0);\
    cin.tie(0);\
    cout.tie(0)\

const int sz = 2e3 + 5;
int a[sz], b[sz], dp[sz][sz], f[sz][sz], n, m;
pii p[sz][sz];

signed main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= m; i++){
        cin >> b[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i] == b[j]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
                p[i][j] = {i - 1, j - 1};
                if(dp[i][j] == 1){
                    f[i][j] = a[i];
                }
            }
            else{
                if(dp[i - 1][j] == dp[i][j - 1]){
                    if(f[i - 1][j] < f[j - 1][i]){
                        f[i][j] = f[i - 1][j];
                        p[i][j] = {i - 1, j};
                    }
                    else{
                        f[i][j] = f[i][j - 1];
                        p[i][j] = {i, j - 1};
                    }
                }
                if(dp[i - 1][j] > dp[i][j - 1]){
                    dp[i][j] = dp[i - 1][j];
                    p[i][j] = {i - 1, j};
                    f[i][j] = f[i - 1][j];
                }
                else{
                    dp[i][j] = dp[i][j-  1];
                    p[i][j] = {i, j - 1};
                    f[i][j] = f[i][j - 1];
                }
            }
        }
    }
    vi v;
    int x = n, y = m;
    while(x != 0 and y != 0){
        int xx = p[x][y].first, yy= p[x][y].second;
        if(dp[x][y] == dp[xx][yy] + 1){
            v.push_back(a[x]);
        }
        x = xx, y = yy;
    }
    reverse(all(v));
    if(v.size() == 0){
        cout << n + m << endl;
        if(a[1] < b[1]){
            for(int i = 1; i <= n; i++)   cout << a[i] << " ";
            for(int i = 1; i <= m; i++)   cout << b[i] << " ";
        }
        else{
            for(int i = 1; i <= m; i++)   cout << b[i] << " ";
            for(int i = 1; i <= n; i++)   cout << a[i] << " ";
        }
        return 0;
    }
    vi res;
    int i = 1, j = 1, ind = 0;
    while(i <= n and j <= m and ind < v.size()){
        if(a[i] < b[j]){
            while(a[i] != v[ind] and i <= n)    res.push_back(a[i++]);
            while(b[j] != v[ind] and j <= m)    res.push_back(b[j++]);
        }
        else{
            while(b[j] != v[ind] and j <= m)    res.push_back(b[j++]);
            while(a[i] != v[ind] and i <= n)    res.push_back(a[i++]);
        }
        res.push_back(v[ind++]);
        i++, j++;
    }
    while(i <= n)    res.push_back(a[i++]);
    while(j <= m)   res.push_back(b[j++]);
    cout << res.size() << endl;
    for(int i : res){
        cout << i << " ";
    }
}

Compilation message (stderr)

Crypto.cpp: In function 'int main()':
Crypto.cpp:87:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     while(i <= n and j <= m and ind < v.size()){
      |                                 ~~~~^~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 9
• Subtask 3: 0 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 21
• Subtask 6: 0 / 13
• Subtask 7: 0 / 19
• Subtask 8: 0 / 12