oj.uz

Submission #661287

# Submission time Handle Problem Language Result Execution time Memory
661287 2022-11-25T10:24:32 Z bebra Spirale (COCI18_spirale) C++17
80 / 80
 11 ms 2460 KB 
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> a(n, vector<int>(m, -1));
    int cnt_used = 0;
    vector<tuple<int, int, int>> spirals(k);
    for (auto& [x, y, dir] : spirals) {
        cin >> x >> y >> dir;
        --x, --y;
    }
    // 1 - up, 2 - down, 3 - left, 4 - right
    vector<set<pair<int, int>>> used_cells(k);
    vector<vector<int>> nxt(2, vector<int>(5));
    vector<pair<int, int>> moves(5);
    moves[1] = {-1, 0};
    moves[2] = {1, 0};
    moves[3] = {0, -1};
    moves[4] = {0, 1};
    nxt[1] = {1, 3, 4, 2, 1};
    nxt[0] = {1, 4, 3, 1, 2};
    vector<int> last_step(k);
    for (int step = 1; step <= 10000; ++step) {
        if (cnt_used >= n * m) break;
        int i = 0;
        for (auto& [x, y, dir] : spirals) {
            if (x >= 0 && x < n && y >= 0 && y < m) {
                if (a[x][y] == -1) {
                    ++cnt_used;
                    a[x][y] = step;
                }
            }
            used_cells[i].emplace(x, y);
            auto [dx, dy] = moves[nxt[dir][last_step[i]]];
            if (used_cells[i].count({x + dx, y + dy})) {
                auto [dx2, dy2] = moves[last_step[i]];
                x += dx2;
                y += dy2;
            } else {
                x += dx;
                y += dy;
                last_step[i] = nxt[dir][last_step[i]];
            }
            ++i;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << a[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 11 ms 2460 KB Output is correct