oj.uz

Submission #243641

# Submission time Handle Problem Language Result Execution time Memory
243641 2020-07-01T13:02:09 Z Vimmer Pohlepko (COCI16_pohlepko) C++14
80 / 80
 36 ms 16384 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 1000001
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 2> a2;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


bool mk1[2005][2005], mk2[2005][2005];

int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m;

    cin >> n >> m;

    string s[n];

    for (int i = 0; i < n; i++) cin >> s[i];

    string str = "";

    int i = 0, j = 0;

    str += s[0][0];

    while (i != n - 1 || j != m - 1)
    {
        char mn = 'z';

        int cx = 0, cy = 0;

        if (i + 1 != n) {mn = s[i + 1][j]; cx++;}

        if (j + 1 != m && mn - 'a' > s[i][j + 1] - 'a') {mn = s[i][j + 1]; cx = 0; cy++;}

        if (i + 1 != n && j + 1 != m && s[i][j + 1] == s[i + 1][j])
        {
            string s1 = "", s2 = "";

            s1 += s[i][j + 1];

            s2 += s[i + 1][j];

            vector <pair <int, int> > g1, g2; g1.clear(); g2.clear(); g1.pb({i + 1, j}); g2.pb({i, j + 1});

            while (1)
            {
                char mn1 = 'z', mn2 = 'z';

                pair <int, int> ps1, ps2;

                vector <pair <int, int> > n1, n2; n1.clear(); n2.clear();

                for (auto it : g1)
                    {
                        if (it.F + 1 != n && !mk1[it.F + 1][it.S]) {mk1[it.F + 1][it.S] = 1; n1.pb({it.F + 1, it.S}); if (mn1 - 'a' >= s[it.F + 1][it.S] - 'a') {mn1 = s[it.F + 1][it.S]; ps1 = {it.F + 1, it.S};}}

                        if (it.S + 1 != m && !mk1[it.F][it.S + 1]) {mk1[it.F][it.S + 1] = 1; n1.pb({it.F, it.S + 1}); if (mn1 - 'a' >= s[it.F][it.S + 1] - 'a') {mn1 = s[it.F][it.S + 1]; ps1 = {it.F, it.S + 1};}}
                    }

                for (auto it : g2)
                    {
                        if (it.F + 1 != n && !mk2[it.F + 1][it.S]) {mk2[it.F + 1][it.S] = 1; n2.pb({it.F + 1, it.S}); if (mn2 - 'a' >= s[it.F + 1][it.S] - 'a') {mn2 = s[it.F + 1][it.S]; ps2 = {it.F + 1, it.S};}}

                        if (it.S + 1 != m && !mk2[it.F][it.S + 1]) {mk2[it.F][it.S + 1] = 1; n2.pb({it.F, it.S + 1}); if (mn2 - 'a' >= s[it.F][it.S + 1] - 'a') {mn2 = s[it.F][it.S + 1]; ps2 = {it.F, it.S + 1};}}
                    }

                if (sz(n1) == 0) {str += s1; cout << str << endl; exit(0);}

                s1 += mn1;

                s2 += mn2;

                if (mn1 != mn2)
                {
                    if (mn1 - 'a' > mn2 - 'a') {i = ps2.F; j = ps2.S; str += s2;}
                      else {i = ps1.F; j = ps1.S; str += s1;}

                    break;
                }

                vector <pair <int, int> > gr; gr.clear();

                for (auto it : n1)
                    if (s[it.F][it.S] == mn1) gr.pb(it);

                g1 = gr;

                gr.clear();

                for (auto it : n2)
                    if (s[it.F][it.S] == mn2) gr.pb(it);

                g2 = gr;
            }

            continue;
        }

        i += cx; j += cy;

        str += mn;
    }

    cout << str << endl;
}

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 8 ms 3072 KB Output is correct
8 Correct 14 ms 8576 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 7 ms 1280 KB Output is correct
11 Correct 5 ms 1024 KB Output is correct
12 Correct 8 ms 4992 KB Output is correct
13 Correct 11 ms 8576 KB Output is correct
14 Correct 21 ms 16384 KB Output is correct
15 Correct 6 ms 768 KB Output is correct
16 Correct 36 ms 9496 KB Output is correct