oj.uz

답안 #826491

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
826491 2023-08-15T15:57:10 Z nasir_bashirov Cryptography (NOI20_crypto) C++11
0 / 100
 1000 ms 212 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1072 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1072 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1039 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1072 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1072 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -