oj.uz

답안 #572817

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
572817 2022-06-05T10:33:17 Z baluteshih 화성 (APIO22_mars) C++17
21 / 100
 43 ms 2924 KB 
#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back

char mp[100][100];
pii boss[100][100];
pii mapping[100000];

pii finds(pii a) {
    if (a == pii(-1, -1)) return pii(-1, -1);
    if (a == boss[a.X][a.Y]) return a;
    return boss[a.X][a.Y] = finds(boss[a.X][a.Y]);
}

int Union(pii a, pii b) {
    a = finds(a), b = finds(b);
    if (a == b)
        return 0;
    if (a > b)
        swap(a, b);
    //cerr << "Union " << a.X << " " << a.Y << " " << b.X << " " << b.Y << "\n";
    boss[b.X][b.Y] = a;
    return 1;
}

string process(vector<vector<string>> a, int i, int j, int k, int n) {
    const int ANS = __lg(((2 * n + 1) * (2 * n + 1) + 1) / 2) + 2;
    const int SZ = 4; 

    auto decode = [&](string s) {
        int rt = 0;
        for (int t = 0; t < SZ(s); ++t)
            if (s[t] == '1')
                rt |= 1 << t;
        return rt;
    };

    auto encode = [](int x, int len) {
        string rt(len, '0');
        for (int t = 0; t < len; ++t)
            if (x >> t & 1)
                rt[t] = '1', x -= 1 << t;
        assert(x == 0);
        return rt;
    };

    int m = 2 * (n - k - 1);
    int num = 2 * n - (m + 2) + 2 * n - (m + 2);
    int nxt = 2 * n - (m) + 2 * n - (m);

    auto place = [&](int p, int q, int tm) {
        if (q == tm + 2)
            return 2 * n - p;
        return 2 * n - (tm + 3) + p - (tm + 2);
    };

    auto coord = [&](int x, int tm) {
        if (x <= 2 * n - (tm + 3))
            return pii(2 * n - x, tm + 2);
        x -= 2 * n - (tm + 3);
        return pii(tm + 2, x + tm + 2);
    };

    auto check = [&](int x, int y) {
        if (x < m || x >= 2 * n + 1) return 0;
        if (y < m || y >= 2 * n + 1) return 0;
        if (x > m + 2 && y > m + 2) return 0;
        if (boss[x][y].X == -1) return 0;
        return 1;
    };

    if (i == m && j == m) {

        if (k == 0 && a[2][2][0] == '1') {
            a[2][2][100 - ANS] = '1';
            a[2][2][1] = '1';
        }

        int sum = decode(a[2][2].substr(100 - ANS, ANS));
        //cerr << "prv sum = " << sum << "\n";
        for (int p = m; p < m + 3; ++p)
            for (int q = m; q < m + 3; ++q) {
                mp[p][q] = a[p - m][q - m][0];
                boss[p][q] = pii(p, q);
                if (mp[p][q] == '1')
                    sum += (p != m + 2 || q != m + 2);
                else
                    boss[p][q] = pii(-1, -1);
            }
        for (int p = m; p < m + 2; ++p)
            for (int q = m + 3; q < 2 * n + 1; ++q) {
                mp[p][q] = a[p - m][2][q - m - 2];
                mp[q][p] = a[2][p - m][q - m - 2];
                boss[p][q] = pii(p, q);
                if (mp[p][q] == '1')
                    ++sum;
                else
                    boss[p][q] = pii(-1, -1);
                boss[q][p] = pii(q, p);
                if (mp[q][p] == '1')
                    ++sum;
                else
                    boss[q][p] = pii(-1, -1);
            }
        //cerr << "sum = " << sum << "\n";
        for (int p = 0; p < num; ++p)
            mapping[p] = pii(2 * n + 1, 2 * n + 1);
        mapping[0] = pii(-1, -1);
        for (int p = 0, nw = 1; p < num; ++p, nw += SZ) {
            int d = decode(a[2][2].substr(nw, SZ));
            pii c = coord(p, m);
            mapping[d] = min(mapping[d], c);
        }
        for (int p = 0, nw = 1; p < num; ++p, nw += SZ) {
            int d = decode(a[2][2].substr(nw, SZ));
            pii c = coord(p, m);
            //cerr << c.X << " " << c.Y << " code = " << d << ", mapping = " << mapping[d].X << " " << mapping[d].Y << "\n";
            boss[c.X][c.Y] = mapping[d];
        }
        /*for (int p = m; p < 2 * n + 1; ++p)
            for (int q = m; q < 2 * n + 1; ++q)
                if (check(p, q)) {
                    cerr << "boss " << p << " " << q << " = " << boss[p][q].X << " " << boss[p][q].Y << "\n";
                }*/
        if (check(m + 2, m + 2)) {
            if (check(m + 3, m + 2))
                Union(pii(m + 2, m + 2), pii(m + 3, m + 2));
            if (check(m + 2, m + 3))
                Union(pii(m + 2, m + 2), pii(m + 2, m + 3));
        }
        for (int p = m; p < 2 * n + 1; ++p)
            for (int q = m; q < 2 * n + 1; ++q)
                if (check(p, q)) {
                    if (check(p + 1, q))
                        sum -= Union(pii(p, q), pii(p + 1, q));
                    if (check(p, q + 1))
                        sum -= Union(pii(p, q), pii(p, q + 1));
                }
        if (k == n - 1)
            return encode(sum, ANS) + string(100 - ANS, '0');
        string rt(1, a[0][0][0]);

        vector<pii> ele(1, pii(-1, -1));
        for (int p = 0; p < nxt; ++p) {
            pii c = coord(p, m - 2);
            ele.pb(finds(c));
        }
        sort(ALL(ele)), ele.resize(unique(ALL(ele)) - ele.begin());
        for (int p = 0; p < nxt; ++p) {
            pii c = coord(p, m - 2);
            rt += encode(lower_bound(ALL(ele), finds(c)) - ele.begin(), SZ);
        }

        rt.resize(100 - ANS, '0');
        return rt + encode(sum, ANS);
    }
    if (i == m) {
        a[2][0].pop_back(), a[2][0].pop_back();
        a[2][0].insert(a[2][0].begin(), a[1][0][0]);
        a[2][0].insert(a[2][0].begin(), a[0][0][0]);
        return a[2][0];
    }
    if (j == m) {
        a[0][2].pop_back(), a[0][2].pop_back();
        a[0][2].insert(a[0][2].begin(), a[0][1][0]);
        a[0][2].insert(a[0][2].begin(), a[0][0][0]);
        return a[0][2];
    }
    return a[0][0];
}

Compilation message

mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:59:10: warning: variable 'place' set but not used [-Wunused-but-set-variable]
   59 |     auto place = [&](int p, int q, int tm) {
      |          ^~~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct

Subtask #4
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct
21 Incorrect 8 ms 348 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct
21 Incorrect 8 ms 348 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct
21 Incorrect 8 ms 348 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct
21 Incorrect 8 ms 348 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct
21 Incorrect 8 ms 348 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct
21 Incorrect 8 ms 348 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct
21 Incorrect 8 ms 348 KB Incorrect
22 Halted 0 ms 0 KB -