oj.uz

Submission #786010

# Submission time Handle Problem Language Result Execution time Memory
786010 2023-07-17T22:02:43 Z sadsa Stray Cat (JOI20_stray) C++17
5 / 100
 511 ms 15580 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;

using i64 = int64_t;
using vl = vector<i64>;
using ll = pair<i64, i64>;
using vll = vector<ll>;

constexpr int iINF = numeric_limits<int>::max();
constexpr i64 lINF = numeric_limits<i64>::max();

#define RANGE(x) begin(x), end(x)

template <typename... T>
void DBG(T&&... args) {
    ((cerr << args << ' '), ...) << '\n';
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &vec) {
    out << '{';
    for (size_t i = 0; i < vec.size()-1; ++i)
        out << vec[i] << ", ";
    out << vec.back() << '}';
    return out;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &pr) {
    out << '(' << pr.first << ", " << pr.second << ')';
    return out;
}

namespace {

vi Mark2d(int N, vi &U, vi &V) {
    int M = N-1;
    vi X(M, -1);

    vector<vector<pair<int,int>>> adj(N);

    for (int i = 0; i < M; ++i) {
        adj[U[i]].emplace_back(V[i], i);
        adj[V[i]].emplace_back(U[i], i);
    }

    DBG(adj);

    const vi sequence {1,0,1,0,0,1};

    queue<ii> q;

    for (auto [nxt, edge] : adj[0]) {
        X[edge] = sequence[0];
        q.emplace(nxt, 1);
    }

    DBG("Mark");

    while (!q.empty()) {
        auto [crt, counter] = q.front();
        q.pop();

        DBG(crt, counter);

        if (adj[crt].size() == 1) continue;
        if (adj[crt].size() == 2) {
            for (auto [nxt, edge] : adj[crt]) {
                if (X[edge] == -1) {
                    X[edge] = sequence[counter % sequence.size()];
                    q.emplace(nxt, counter+1);
                }
            }
        } else {
            int x = !sequence[(counter-1) % sequence.size()];
            for (auto [nxt, edge] : adj[crt]) {
                if (X[edge] == -1) {
                    X[edge] = x;
                    q.emplace(nxt, x);
                }
            }
        }
    }

    DBG(X);
    return X;

}

}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
    if (N == M+1) return Mark2d(N, U, V);
    while (1);
}

/*
7 6 2 6 3
6 5
5 0
0 1
1 2
2 3
3 4

12 11 2 6 4
6 5
5 0
0 1
1 2
2 3
3 4
4 7
7 8
8 9
9 10
10 11

13 12 2 12 10
0 2
1 2
2 3
3 4
4 5
4 6
6 7
3 8
8 9
8 10
10 11
11 12

*/
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;

using i64 = int64_t;
using vl = vector<i64>;
using ll = pair<i64, i64>;
using vll = vector<ll>;

constexpr int iINF = numeric_limits<int>::max();
constexpr i64 lINF = numeric_limits<i64>::max();

#define RANGE(x) begin(x), end(x)

template <typename... T>
void DBG(T&&... args) {
    ((cerr << args << ' '), ...) << '\n';
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &vec) {
    out << '{';
    for (size_t i = 0; i < vec.size()-1; ++i)
        out << vec[i] << ", ";
    out << vec.back() << '}';
    return out;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &pr) {
    out << '(' << pr.first << ", " << pr.second << ')';
    return out;
}

namespace {

int A, B;

bool found = false, first = true;
string current_path;
const string incr_way = "1101001101001";
const string decr_way = "1100101100101";

int prv = -1;

//             0      1
int move2d(int a, int b) {
    if (first) {
        DBG("FIRST!");
        int r;
        if (a+b == 1) {
            DBG("FOUND! by endpoint");
            found = true;
            r = a? 0: 1;
        } else if (a+b==2) {
            if (a == 2) {
                current_path = "00";
                r = 0;
            } else if (b == 2) {
                current_path = "11";
                r = 1;
            } else {
                current_path = "10";
                r = 0;
            }
        } else {
            DBG("FOUND! by intersection");

            r=-2;// not possible!
            if (a == 1) r = 0;
            if (b == 1) r = 1;
        }

        DBG("DONE FIRST:", r);
        first = false;
        return r;
    }

    if (a+b == 0) { // end point
        DBG("FOUND! by endpoint");
        found = true;
        return -1;
    }

    if (a+b >= 2) {
        DBG("FOUND! by intersection");
        found = true;
        if (a == 0 || b == 0) return -1;

        if (prv) b++;
        else a++;

        if (a == 1) return 0;
        if (b == 1) return 1;

        return -2; // not possible!
    }

    if (!found) {
        current_path += a? '0': '1';

        int correct = decr_way.find(current_path) != string::npos;
        int wrong = incr_way.find(current_path) != string::npos;

        DBG(current_path);
        found = true;
        if (correct + wrong == 2) found = false;
        else if (wrong) {
            DBG("FOUND! by wrong direction");
            return -1;
        }

        if (found) DBG("FOUND! by good direction");
    }

    if (a) return 0;
    else return 1;
}

}  // namespace

void Init(int A, int B) {
    ::A = A;
    ::B = B;
}

int Move(std::vector<int> y) {
    if (A == 2) return prv = move2d(y[0], y[1]);
    return -1;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 476 ms 15580 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 476 ms 15580 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 455 ms 13356 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 455 ms 13356 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 836 KB Output is correct
2 Correct 2 ms 648 KB Output is correct
3 Correct 13 ms 968 KB Output is correct
4 Correct 12 ms 892 KB Output is correct
5 Correct 12 ms 856 KB Output is correct
6 Correct 13 ms 840 KB Output is correct
7 Correct 16 ms 896 KB Output is correct
8 Correct 13 ms 928 KB Output is correct
9 Correct 12 ms 908 KB Output is correct
10 Correct 13 ms 880 KB Output is correct
11 Correct 13 ms 900 KB Output is correct
12 Correct 12 ms 896 KB Output is correct
13 Correct 12 ms 904 KB Output is correct
14 Correct 12 ms 896 KB Output is correct
15 Correct 12 ms 896 KB Output is correct
16 Correct 12 ms 796 KB Output is correct
17 Correct 12 ms 896 KB Output is correct
18 Correct 15 ms 884 KB Output is correct
19 Correct 13 ms 904 KB Output is correct
20 Correct 12 ms 900 KB Output is correct
21 Correct 12 ms 912 KB Output is correct
22 Correct 18 ms 912 KB Output is correct
23 Correct 18 ms 900 KB Output is correct
24 Correct 16 ms 916 KB Output is correct
25 Correct 12 ms 884 KB Output is correct
26 Correct 18 ms 908 KB Output is correct
27 Correct 12 ms 940 KB Output is correct
28 Correct 19 ms 928 KB Output is correct

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 11708 KB Output is correct
2 Correct 468 ms 12640 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 429 ms 11912 KB Output is correct
5 Correct 463 ms 13164 KB Output is correct
6 Correct 483 ms 13304 KB Output is correct
7 Correct 461 ms 12196 KB Output is correct
8 Correct 482 ms 12300 KB Output is correct
9 Correct 497 ms 13348 KB Output is correct
10 Correct 500 ms 13116 KB Output is correct
11 Correct 451 ms 13140 KB Output is correct
12 Correct 440 ms 13124 KB Output is correct
13 Correct 452 ms 13104 KB Output is correct
14 Correct 450 ms 13100 KB Output is correct
15 Correct 452 ms 13156 KB Output is correct
16 Correct 452 ms 13100 KB Output is correct
17 Correct 446 ms 12848 KB Output is correct
18 Correct 447 ms 12776 KB Output is correct
19 Correct 449 ms 13020 KB Output is correct
20 Correct 446 ms 12904 KB Output is correct
21 Correct 449 ms 13100 KB Output is correct
22 Correct 440 ms 12904 KB Output is correct
23 Correct 447 ms 12136 KB Output is correct
24 Correct 452 ms 12088 KB Output is correct
25 Correct 446 ms 12252 KB Output is correct
26 Correct 447 ms 12268 KB Output is correct
27 Correct 454 ms 12952 KB Output is correct
28 Correct 462 ms 12864 KB Output is correct
29 Correct 450 ms 12788 KB Output is correct
30 Correct 456 ms 12856 KB Output is correct
31 Correct 446 ms 12208 KB Output is correct
32 Correct 465 ms 12148 KB Output is correct
33 Correct 457 ms 12232 KB Output is correct
34 Correct 452 ms 12324 KB Output is correct
35 Correct 453 ms 12716 KB Output is correct
36 Correct 457 ms 12720 KB Output is correct
37 Incorrect 511 ms 12628 KB Wrong Answer [6]
38 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 11732 KB Output is correct
2 Correct 445 ms 12400 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 454 ms 11944 KB Output is correct
5 Correct 447 ms 13196 KB Output is correct
6 Correct 437 ms 13116 KB Output is correct
7 Correct 435 ms 12268 KB Output is correct
8 Correct 451 ms 12324 KB Output is correct
9 Correct 445 ms 13188 KB Output is correct
10 Correct 472 ms 13328 KB Output is correct
11 Correct 471 ms 13156 KB Output is correct
12 Correct 442 ms 13112 KB Output is correct
13 Correct 468 ms 13176 KB Output is correct
14 Correct 489 ms 13272 KB Output is correct
15 Correct 459 ms 13248 KB Output is correct
16 Correct 469 ms 13304 KB Output is correct
17 Correct 453 ms 12864 KB Output is correct
18 Correct 467 ms 13288 KB Output is correct
19 Correct 439 ms 12916 KB Output is correct
20 Correct 454 ms 12924 KB Output is correct
21 Correct 442 ms 12896 KB Output is correct
22 Correct 450 ms 12924 KB Output is correct
23 Correct 469 ms 12136 KB Output is correct
24 Correct 448 ms 12260 KB Output is correct
25 Correct 452 ms 12268 KB Output is correct
26 Correct 442 ms 12440 KB Output is correct
27 Correct 451 ms 12820 KB Output is correct
28 Correct 460 ms 12780 KB Output is correct
29 Correct 457 ms 12784 KB Output is correct
30 Correct 457 ms 12848 KB Output is correct
31 Correct 440 ms 12084 KB Output is correct
32 Correct 447 ms 12176 KB Output is correct
33 Correct 439 ms 12280 KB Output is correct
34 Correct 442 ms 12208 KB Output is correct
35 Correct 461 ms 12692 KB Output is correct
36 Incorrect 457 ms 12688 KB Wrong Answer [6]
37 Halted 0 ms 0 KB -