oj.uz

Submission #572815

# Submission time Handle Problem Language Result Execution time Memory
572815 2022-06-05T10:32:16 Z baluteshih Mars (APIO22_mars) C++17
14 / 100
 41 ms 2716 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) + 1;
    const int SZ = 3; 

    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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2052 KB Output is correct
2 Correct 8 ms 2400 KB Output is correct
3 Correct 8 ms 2320 KB Output is correct
4 Correct 8 ms 2312 KB Output is correct
5 Correct 8 ms 2096 KB Output is correct
6 Correct 7 ms 2272 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2052 KB Output is correct
2 Correct 8 ms 2400 KB Output is correct
3 Correct 8 ms 2320 KB Output is correct
4 Correct 8 ms 2312 KB Output is correct
5 Correct 8 ms 2096 KB Output is correct
6 Correct 7 ms 2272 KB Output is correct
7 Correct 8 ms 2400 KB Output is correct
8 Correct 16 ms 2716 KB Output is correct
9 Correct 16 ms 2600 KB Output is correct
10 Correct 17 ms 2532 KB Output is correct
11 Correct 15 ms 2496 KB Output is correct
12 Correct 16 ms 2516 KB Output is correct
13 Correct 16 ms 2688 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2052 KB Output is correct
2 Correct 8 ms 2400 KB Output is correct
3 Correct 8 ms 2320 KB Output is correct
4 Correct 8 ms 2312 KB Output is correct
5 Correct 8 ms 2096 KB Output is correct
6 Correct 7 ms 2272 KB Output is correct
7 Correct 8 ms 2400 KB Output is correct
8 Correct 16 ms 2716 KB Output is correct
9 Correct 16 ms 2600 KB Output is correct
10 Correct 17 ms 2532 KB Output is correct
11 Correct 15 ms 2496 KB Output is correct
12 Correct 16 ms 2516 KB Output is correct
13 Correct 16 ms 2688 KB Output is correct
14 Correct 30 ms 2652 KB Output is correct
15 Correct 41 ms 2692 KB Output is correct
16 Incorrect 5 ms 332 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2052 KB Output is correct
2 Correct 8 ms 2400 KB Output is correct
3 Correct 8 ms 2320 KB Output is correct
4 Correct 8 ms 2312 KB Output is correct
5 Correct 8 ms 2096 KB Output is correct
6 Correct 7 ms 2272 KB Output is correct
7 Correct 8 ms 2400 KB Output is correct
8 Correct 16 ms 2716 KB Output is correct
9 Correct 16 ms 2600 KB Output is correct
10 Correct 17 ms 2532 KB Output is correct
11 Correct 15 ms 2496 KB Output is correct
12 Correct 16 ms 2516 KB Output is correct
13 Correct 16 ms 2688 KB Output is correct
14 Correct 30 ms 2652 KB Output is correct
15 Correct 41 ms 2692 KB Output is correct
16 Incorrect 5 ms 332 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2052 KB Output is correct
2 Correct 8 ms 2400 KB Output is correct
3 Correct 8 ms 2320 KB Output is correct
4 Correct 8 ms 2312 KB Output is correct
5 Correct 8 ms 2096 KB Output is correct
6 Correct 7 ms 2272 KB Output is correct
7 Correct 8 ms 2400 KB Output is correct
8 Correct 16 ms 2716 KB Output is correct
9 Correct 16 ms 2600 KB Output is correct
10 Correct 17 ms 2532 KB Output is correct
11 Correct 15 ms 2496 KB Output is correct
12 Correct 16 ms 2516 KB Output is correct
13 Correct 16 ms 2688 KB Output is correct
14 Correct 30 ms 2652 KB Output is correct
15 Correct 41 ms 2692 KB Output is correct
16 Incorrect 5 ms 332 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2052 KB Output is correct
2 Correct 8 ms 2400 KB Output is correct
3 Correct 8 ms 2320 KB Output is correct
4 Correct 8 ms 2312 KB Output is correct
5 Correct 8 ms 2096 KB Output is correct
6 Correct 7 ms 2272 KB Output is correct
7 Correct 8 ms 2400 KB Output is correct
8 Correct 16 ms 2716 KB Output is correct
9 Correct 16 ms 2600 KB Output is correct
10 Correct 17 ms 2532 KB Output is correct
11 Correct 15 ms 2496 KB Output is correct
12 Correct 16 ms 2516 KB Output is correct
13 Correct 16 ms 2688 KB Output is correct
14 Correct 30 ms 2652 KB Output is correct
15 Correct 41 ms 2692 KB Output is correct
16 Incorrect 5 ms 332 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2052 KB Output is correct
2 Correct 8 ms 2400 KB Output is correct
3 Correct 8 ms 2320 KB Output is correct
4 Correct 8 ms 2312 KB Output is correct
5 Correct 8 ms 2096 KB Output is correct
6 Correct 7 ms 2272 KB Output is correct
7 Correct 8 ms 2400 KB Output is correct
8 Correct 16 ms 2716 KB Output is correct
9 Correct 16 ms 2600 KB Output is correct
10 Correct 17 ms 2532 KB Output is correct
11 Correct 15 ms 2496 KB Output is correct
12 Correct 16 ms 2516 KB Output is correct
13 Correct 16 ms 2688 KB Output is correct
14 Correct 30 ms 2652 KB Output is correct
15 Correct 41 ms 2692 KB Output is correct
16 Incorrect 5 ms 332 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2052 KB Output is correct
2 Correct 8 ms 2400 KB Output is correct
3 Correct 8 ms 2320 KB Output is correct
4 Correct 8 ms 2312 KB Output is correct
5 Correct 8 ms 2096 KB Output is correct
6 Correct 7 ms 2272 KB Output is correct
7 Correct 8 ms 2400 KB Output is correct
8 Correct 16 ms 2716 KB Output is correct
9 Correct 16 ms 2600 KB Output is correct
10 Correct 17 ms 2532 KB Output is correct
11 Correct 15 ms 2496 KB Output is correct
12 Correct 16 ms 2516 KB Output is correct
13 Correct 16 ms 2688 KB Output is correct
14 Correct 30 ms 2652 KB Output is correct
15 Correct 41 ms 2692 KB Output is correct
16 Incorrect 5 ms 332 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2052 KB Output is correct
2 Correct 8 ms 2400 KB Output is correct
3 Correct 8 ms 2320 KB Output is correct
4 Correct 8 ms 2312 KB Output is correct
5 Correct 8 ms 2096 KB Output is correct
6 Correct 7 ms 2272 KB Output is correct
7 Correct 8 ms 2400 KB Output is correct
8 Correct 16 ms 2716 KB Output is correct
9 Correct 16 ms 2600 KB Output is correct
10 Correct 17 ms 2532 KB Output is correct
11 Correct 15 ms 2496 KB Output is correct
12 Correct 16 ms 2516 KB Output is correct
13 Correct 16 ms 2688 KB Output is correct
14 Correct 30 ms 2652 KB Output is correct
15 Correct 41 ms 2692 KB Output is correct
16 Incorrect 5 ms 332 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2052 KB Output is correct
2 Correct 8 ms 2400 KB Output is correct
3 Correct 8 ms 2320 KB Output is correct
4 Correct 8 ms 2312 KB Output is correct
5 Correct 8 ms 2096 KB Output is correct
6 Correct 7 ms 2272 KB Output is correct
7 Correct 8 ms 2400 KB Output is correct
8 Correct 16 ms 2716 KB Output is correct
9 Correct 16 ms 2600 KB Output is correct
10 Correct 17 ms 2532 KB Output is correct
11 Correct 15 ms 2496 KB Output is correct
12 Correct 16 ms 2516 KB Output is correct
13 Correct 16 ms 2688 KB Output is correct
14 Correct 30 ms 2652 KB Output is correct
15 Correct 41 ms 2692 KB Output is correct
16 Incorrect 5 ms 332 KB Incorrect
17 Halted 0 ms 0 KB -