oj.uz

Submission #165925

# Submission time Handle Problem Language Result Execution time Memory
165925 2019-11-29T15:20:33 Z _qVp_ Pohlepko (COCI16_pohlepko) C++14
80 / 80
 41 ms 12536 KB 
#include <bits/stdc++.h>

using namespace std;

const int md = 2e3 + 10;

int dx[] = {1, 0};
int dy[] = {0, 1};

struct node {
    char c;
    int x, y;
};

vector < node > ans;
vector < pair < int, int > > v[md];
string s[md];
string res;
int n, m;
bool dd[md][md];

bool inside(int x, int y) {
    return (x >= 0 && x < n && y >= 0 && y < m);
}

bool cmp(node a, node b) {
    return a.c < b.c;
}

int main() {
    //freopen("test.in", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++) 
        cin >> s[i];
    res = s[0][0];
    v[0].push_back({0, 0});
    for(int j = 1; j < m + n - 1; j++) {
        int cur = j & 1, pre = 1 - cur;
        v[cur].clear();
        ans.clear();
        for(int i = 0; i < v[pre].size(); i++) {
            int row = v[pre][i].first, col = v[pre][i].second;
            for(int k = 0; k < 2; k++) {
                int nr = row + dx[k];
                int nc = col + dy[k];
                if (inside(nr, nc) && !dd[nr][nc]) {
                    dd[nr][nc] = 1;
                    ans.push_back({s[nr][nc], nr, nc});
                }
            }
        }
        sort(ans.begin(), ans.end(), cmp);
        //for(int i = 0; i < ans.size(); i++)
        //    cout << "(" << ans[i].x << " " << ans[i].y << " " << ans[i].c << ") ";
        //cout  << endl;
        res += ans[0].c;
        v[cur].push_back({ans[0].x, ans[0].y});
        for(int i = 1; i < ans.size() && ans[i].c == ans[0].c; i++)
            v[cur].push_back({ans[i].x, ans[i].y});
    }
    cout << res;
    return 0;
}

Compilation message

pohlepko.cpp: In function 'int main()':
pohlepko.cpp:42:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < v[pre].size(); i++) {
                        ~~^~~~~~~~~~~~~~~
pohlepko.cpp:59:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 1; i < ans.size() && ans[i].c == ans[0].c; i++)
                        ~~^~~~~~~~~~~~

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 3 ms 1400 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 4 ms 1660 KB Output is correct
7 Correct 10 ms 5756 KB Output is correct
8 Correct 23 ms 12536 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 6 ms 3112 KB Output is correct
13 Correct 8 ms 4856 KB Output is correct
14 Correct 20 ms 12536 KB Output is correct
15 Correct 3 ms 760 KB Output is correct
16 Correct 41 ms 6776 KB Output is correct