| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 785989 |
2023-07-17T21:36:43 Z |
sadsa |
Stray Cat (JOI20_stray) |
C++17 |
|
3000 ms |
724 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], &X[0]+i);
adj[V[i]].emplace_back(U[i], &X[0]+i);
}
const vi sequence {1,0,1,0,0,1};
queue<ii> q;
for (auto [nxt, edge] : adj[0]) {
*edge = sequence[0];
q.emplace(nxt, 1);
}
DBG("Mark");
while (!q.empty()) {
auto [crt, counter] = q.front();
q.pop();
if (adj[crt].size() == 1) break;
if (adj[crt].size() == 2) {
for (auto [nxt, edge] : adj[crt]) {
if (*edge == -1) {
*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 (*edge == -1) {
*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
*/
#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3057 ms |
724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3057 ms |
724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3045 ms |
724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3045 ms |
724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3063 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3042 ms |
724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3050 ms |
724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
