#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
/*
refs:
edi
https://codeforces.com/blog/entry/74871?#comment-591498
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
#include "Anthony.h"
namespace anthony {
set<string> st1,st2;
string chain = "";
void precalc(){
int n = 6;
rep(mask,1<<n){
string s(2*n,'?');
rep(i,n){
ll b = 0;
if(mask&(1<<i)){
b = 1;
}
s[i] = s[i+n] = char('0'+b);
}
st1.clear(), st2.clear();
rep(i,n){
string t = string(s.begin()+i,s.begin()+i+5);
st1.insert(t);
reverse(all(t));
st2.insert(t);
}
bool ok = true;
trav(t,st1){
if(st2.count(t)){
ok = false;
}
}
if(ok){
chain = string(s.begin(),s.begin()+n);
return;
}
}
}
vector<pii> adj[N];
vector<int> val;
void dfs1(int u, int p, int prev_typ, int ptr){
for(auto [v,id] : adj[u]){
if(v == p) conts;
if(sz(adj[v]) == 2){
int nxt_ptr = 0;
if(ptr != -1){
nxt_ptr = (ptr+1)%6;
}
else{
if(prev_typ == 0){
nxt_ptr = 0;
}
else{
nxt_ptr = 2;
}
}
val[id] = chain[nxt_ptr]-'0';
dfs1(v,u,-1,nxt_ptr);
}
else{
int nxt_typ = 0;
if(prev_typ != -1){
nxt_typ = prev_typ^1;
}
else{
nxt_typ = (chain[ptr]-'0')^1;
}
val[id] = nxt_typ;
dfs1(v,u,nxt_typ,-1);
}
}
}
void bfs(){
queue<int> q;
vector<int> dis(N);
vector<bool> vis(N);
q.push(0);
vis[0] = 1;
while(!q.empty()){
int u = q.front();
q.pop();
for(auto [v,id] : adj[u]){
if(vis[v]) conts;
q.push(v);
dis[v] = dis[u]+1;
vis[v] = 1;
}
}
rep(u,N){
for(auto [v,id] : adj[u]){
if(dis[u] > dis[v]) conts;
if(dis[u] == dis[v]){
val[id] = (dis[v]+1)%3;
}
else{
val[id] = dis[v]%3;
}
}
}
}
} // namespace
using namespace anthony;
std::vector<int> Mark(int n, int m, int A, int B,
std::vector<int> U, std::vector<int> V) {
// std::vector<int> X(M);
// for (int i = 0; i < M; ++i) {
// X[i] = FunctionExample(i, A);
// }
// return X;
amin(A,3);
precalc();
rep(i,m){
int u = U[i], v = V[i];
adj[u].pb({v,i}), adj[v].pb({u,i});
}
val = vector<int>(m);
if(A == 3){
bfs();
}
else{
dfs1(0,-1,1,-1);
}
return val;
}
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
// #ifdef LOCAL
// #include "debug.h"
// #else
// #define debug(x) 42
// #endif
/*
refs:
edi
https://codeforces.com/blog/entry/74871?#comment-591498
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
#include "Catherine.h"
namespace catherine {
int A,B;
set<string> st1,st2;
string chain = "";
void precalc(){
int n = 6;
rep(mask,1<<n){
string s(2*n,'?');
rep(i,n){
ll b = 0;
if(mask&(1<<i)){
b = 1;
}
s[i] = s[i+n] = char('0'+b);
}
st1.clear(), st2.clear();
rep(i,n){
string t = string(s.begin()+i,s.begin()+i+5);
st1.insert(t);
reverse(all(t));
st2.insert(t);
}
bool ok = true;
trav(t,st1){
if(st2.count(t)){
ok = false;
}
}
if(ok){
chain = string(s.begin(),s.begin()+n);
return;
}
}
}
int move_num = 0;
bool decided = false;
int prev_edge = 0;
string curr_chain = "";
} // namespace
using namespace catherine;
void Init(int A_, int B_) {
A = min(A_,3);
B = B_;
precalc();
}
int Move(std::vector<int> y) {
// ++variable_example;
// for (int j = 0; j < A; ++j) {
// if (y[j] != 0) {
// return j;
// }
// }
// return -1;
move_num++;
if(A == 3){
if(move_num > 1){
prev_edge = (prev_edge-1+3)%3;
return prev_edge;
}
int active_cnt = 0, active_guy = -1;
rep(i,3){
if(y[i]){
active_cnt++;
active_guy = i;
}
}
if(active_cnt == 1) return prev_edge = active_guy;
int good = -1;
rep(i,3){
if(y[i] and y[(i+1)%3]){
good = i;
}
}
return prev_edge = good;
}
int sum = y[0]+y[1];
if(!sum){
decided = true;
return -1;
}
if(decided){
if(sum == 1){
if(y[0]) prev_edge = 0;
else prev_edge = 1;
}
else{
prev_edge ^= 1;
}
return prev_edge;
}
if(move_num == 1){
if(sum == 1){
if(y[0]) prev_edge = 0;
else prev_edge = 1;
decided = true;
return prev_edge;
}
else if(sum >= 3){
if(y[0] == 1) prev_edge = 0;
else prev_edge = 1;
decided = true;
return prev_edge;
}
else{
if(y[0]) prev_edge = 0;
else prev_edge = 1;
y[prev_edge]--;
if(y[0]) curr_chain.pb('0');
else curr_chain.pb('1');
curr_chain.pb(char('0'+prev_edge));
return prev_edge;
}
}
if(sum >= 2){
decided = true;
y[prev_edge]++;
int nxt_edge = 0;
if(y[0] == 1) nxt_edge = 0;
else nxt_edge = 1;
if(nxt_edge == prev_edge) return -1;
else return prev_edge = nxt_edge;
}
if(y[0]) prev_edge = 0;
else prev_edge = 1;
if(move_num == 4){
curr_chain.pb(char('0'+prev_edge));
assert(sz(curr_chain) == 5);
decided = true;
if(st1.count(curr_chain)){
// wrong direction
curr_chain.pop_back();
prev_edge = curr_chain.back()-'0';
return -1;
}
else{
return prev_edge;
}
}
curr_chain.pb(char('0'+prev_edge));
return prev_edge;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
17924 KB |
Output is correct |
2 |
Correct |
2 ms |
3492 KB |
Output is correct |
3 |
Correct |
24 ms |
17288 KB |
Output is correct |
4 |
Correct |
39 ms |
18828 KB |
Output is correct |
5 |
Correct |
43 ms |
18804 KB |
Output is correct |
6 |
Correct |
30 ms |
17784 KB |
Output is correct |
7 |
Correct |
36 ms |
17848 KB |
Output is correct |
8 |
Correct |
35 ms |
18524 KB |
Output is correct |
9 |
Correct |
36 ms |
18476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
17924 KB |
Output is correct |
2 |
Correct |
2 ms |
3492 KB |
Output is correct |
3 |
Correct |
24 ms |
17288 KB |
Output is correct |
4 |
Correct |
39 ms |
18828 KB |
Output is correct |
5 |
Correct |
43 ms |
18804 KB |
Output is correct |
6 |
Correct |
30 ms |
17784 KB |
Output is correct |
7 |
Correct |
36 ms |
17848 KB |
Output is correct |
8 |
Correct |
35 ms |
18524 KB |
Output is correct |
9 |
Correct |
36 ms |
18476 KB |
Output is correct |
10 |
Correct |
32 ms |
15952 KB |
Output is correct |
11 |
Correct |
34 ms |
15872 KB |
Output is correct |
12 |
Correct |
31 ms |
15804 KB |
Output is correct |
13 |
Correct |
26 ms |
15752 KB |
Output is correct |
14 |
Correct |
32 ms |
16396 KB |
Output is correct |
15 |
Correct |
35 ms |
16572 KB |
Output is correct |
16 |
Correct |
37 ms |
18584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
15624 KB |
Output is correct |
2 |
Correct |
2 ms |
3760 KB |
Output is correct |
3 |
Correct |
25 ms |
15032 KB |
Output is correct |
4 |
Correct |
37 ms |
16844 KB |
Output is correct |
5 |
Correct |
43 ms |
16748 KB |
Output is correct |
6 |
Correct |
38 ms |
15552 KB |
Output is correct |
7 |
Correct |
33 ms |
15596 KB |
Output is correct |
8 |
Correct |
30 ms |
16216 KB |
Output is correct |
9 |
Correct |
39 ms |
16124 KB |
Output is correct |
10 |
Correct |
38 ms |
15888 KB |
Output is correct |
11 |
Correct |
34 ms |
15880 KB |
Output is correct |
12 |
Correct |
28 ms |
15972 KB |
Output is correct |
13 |
Correct |
34 ms |
16056 KB |
Output is correct |
14 |
Correct |
34 ms |
16204 KB |
Output is correct |
15 |
Correct |
31 ms |
16276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
15624 KB |
Output is correct |
2 |
Correct |
2 ms |
3760 KB |
Output is correct |
3 |
Correct |
25 ms |
15032 KB |
Output is correct |
4 |
Correct |
37 ms |
16844 KB |
Output is correct |
5 |
Correct |
43 ms |
16748 KB |
Output is correct |
6 |
Correct |
38 ms |
15552 KB |
Output is correct |
7 |
Correct |
33 ms |
15596 KB |
Output is correct |
8 |
Correct |
30 ms |
16216 KB |
Output is correct |
9 |
Correct |
39 ms |
16124 KB |
Output is correct |
10 |
Correct |
38 ms |
15888 KB |
Output is correct |
11 |
Correct |
34 ms |
15880 KB |
Output is correct |
12 |
Correct |
28 ms |
15972 KB |
Output is correct |
13 |
Correct |
34 ms |
16056 KB |
Output is correct |
14 |
Correct |
34 ms |
16204 KB |
Output is correct |
15 |
Correct |
31 ms |
16276 KB |
Output is correct |
16 |
Correct |
32 ms |
14244 KB |
Output is correct |
17 |
Correct |
27 ms |
14068 KB |
Output is correct |
18 |
Correct |
28 ms |
14088 KB |
Output is correct |
19 |
Correct |
28 ms |
13920 KB |
Output is correct |
20 |
Correct |
36 ms |
14520 KB |
Output is correct |
21 |
Correct |
34 ms |
14388 KB |
Output is correct |
22 |
Correct |
32 ms |
16408 KB |
Output is correct |
23 |
Correct |
30 ms |
14148 KB |
Output is correct |
24 |
Correct |
27 ms |
14044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3744 KB |
Output is correct |
2 |
Correct |
1 ms |
3368 KB |
Output is correct |
3 |
Correct |
2 ms |
3508 KB |
Output is correct |
4 |
Correct |
3 ms |
3364 KB |
Output is correct |
5 |
Correct |
2 ms |
3364 KB |
Output is correct |
6 |
Correct |
3 ms |
3356 KB |
Output is correct |
7 |
Correct |
2 ms |
3364 KB |
Output is correct |
8 |
Correct |
2 ms |
3356 KB |
Output is correct |
9 |
Correct |
2 ms |
3488 KB |
Output is correct |
10 |
Correct |
2 ms |
3356 KB |
Output is correct |
11 |
Correct |
2 ms |
3368 KB |
Output is correct |
12 |
Correct |
2 ms |
3356 KB |
Output is correct |
13 |
Correct |
3 ms |
3632 KB |
Output is correct |
14 |
Correct |
2 ms |
3684 KB |
Output is correct |
15 |
Correct |
2 ms |
3608 KB |
Output is correct |
16 |
Correct |
3 ms |
3540 KB |
Output is correct |
17 |
Correct |
2 ms |
3356 KB |
Output is correct |
18 |
Correct |
2 ms |
3492 KB |
Output is correct |
19 |
Correct |
3 ms |
3348 KB |
Output is correct |
20 |
Correct |
2 ms |
3628 KB |
Output is correct |
21 |
Correct |
2 ms |
3348 KB |
Output is correct |
22 |
Correct |
2 ms |
3360 KB |
Output is correct |
23 |
Correct |
1 ms |
3500 KB |
Output is correct |
24 |
Correct |
3 ms |
3904 KB |
Output is correct |
25 |
Correct |
2 ms |
3356 KB |
Output is correct |
26 |
Correct |
3 ms |
3400 KB |
Output is correct |
27 |
Correct |
2 ms |
3364 KB |
Output is correct |
28 |
Correct |
2 ms |
3364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
13876 KB |
Output is correct |
2 |
Correct |
35 ms |
14832 KB |
Output is correct |
3 |
Correct |
2 ms |
3104 KB |
Output is correct |
4 |
Correct |
24 ms |
13496 KB |
Output is correct |
5 |
Correct |
30 ms |
16448 KB |
Output is correct |
6 |
Correct |
40 ms |
16480 KB |
Output is correct |
7 |
Correct |
27 ms |
15376 KB |
Output is correct |
8 |
Correct |
30 ms |
15464 KB |
Output is correct |
9 |
Correct |
37 ms |
16368 KB |
Output is correct |
10 |
Correct |
40 ms |
16324 KB |
Output is correct |
11 |
Correct |
40 ms |
16516 KB |
Output is correct |
12 |
Correct |
30 ms |
16692 KB |
Output is correct |
13 |
Correct |
34 ms |
16464 KB |
Output is correct |
14 |
Correct |
33 ms |
16344 KB |
Output is correct |
15 |
Correct |
39 ms |
16484 KB |
Output is correct |
16 |
Correct |
33 ms |
16472 KB |
Output is correct |
17 |
Correct |
34 ms |
16132 KB |
Output is correct |
18 |
Correct |
38 ms |
16212 KB |
Output is correct |
19 |
Correct |
28 ms |
16076 KB |
Output is correct |
20 |
Correct |
28 ms |
16196 KB |
Output is correct |
21 |
Correct |
30 ms |
15932 KB |
Output is correct |
22 |
Correct |
33 ms |
16208 KB |
Output is correct |
23 |
Correct |
26 ms |
13628 KB |
Output is correct |
24 |
Correct |
27 ms |
13780 KB |
Output is correct |
25 |
Correct |
27 ms |
14352 KB |
Output is correct |
26 |
Correct |
34 ms |
13908 KB |
Output is correct |
27 |
Correct |
30 ms |
14840 KB |
Output is correct |
28 |
Correct |
33 ms |
14980 KB |
Output is correct |
29 |
Correct |
33 ms |
15140 KB |
Output is correct |
30 |
Correct |
33 ms |
14860 KB |
Output is correct |
31 |
Correct |
30 ms |
13640 KB |
Output is correct |
32 |
Correct |
32 ms |
13984 KB |
Output is correct |
33 |
Correct |
31 ms |
14152 KB |
Output is correct |
34 |
Correct |
32 ms |
14116 KB |
Output is correct |
35 |
Correct |
28 ms |
14848 KB |
Output is correct |
36 |
Correct |
33 ms |
15032 KB |
Output is correct |
37 |
Correct |
33 ms |
15052 KB |
Output is correct |
38 |
Correct |
34 ms |
14900 KB |
Output is correct |
39 |
Correct |
36 ms |
14736 KB |
Output is correct |
40 |
Correct |
30 ms |
14840 KB |
Output is correct |
41 |
Correct |
32 ms |
15480 KB |
Output is correct |
42 |
Correct |
38 ms |
15804 KB |
Output is correct |
43 |
Correct |
35 ms |
15364 KB |
Output is correct |
44 |
Correct |
30 ms |
15500 KB |
Output is correct |
45 |
Correct |
42 ms |
15376 KB |
Output is correct |
46 |
Correct |
32 ms |
15424 KB |
Output is correct |
47 |
Correct |
32 ms |
14656 KB |
Output is correct |
48 |
Correct |
27 ms |
14532 KB |
Output is correct |
49 |
Correct |
27 ms |
14408 KB |
Output is correct |
50 |
Correct |
27 ms |
14656 KB |
Output is correct |
51 |
Correct |
25 ms |
13952 KB |
Output is correct |
52 |
Correct |
30 ms |
14156 KB |
Output is correct |
53 |
Correct |
26 ms |
14144 KB |
Output is correct |
54 |
Correct |
27 ms |
14072 KB |
Output is correct |
55 |
Correct |
27 ms |
13864 KB |
Output is correct |
56 |
Correct |
27 ms |
13996 KB |
Output is correct |
57 |
Correct |
33 ms |
13936 KB |
Output is correct |
58 |
Correct |
26 ms |
14120 KB |
Output is correct |
59 |
Correct |
33 ms |
14020 KB |
Output is correct |
60 |
Correct |
31 ms |
13880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
13848 KB |
Output is correct |
2 |
Correct |
36 ms |
14552 KB |
Output is correct |
3 |
Correct |
1 ms |
3092 KB |
Output is correct |
4 |
Correct |
25 ms |
13332 KB |
Output is correct |
5 |
Correct |
40 ms |
16472 KB |
Output is correct |
6 |
Correct |
37 ms |
16364 KB |
Output is correct |
7 |
Correct |
26 ms |
15444 KB |
Output is correct |
8 |
Correct |
27 ms |
15440 KB |
Output is correct |
9 |
Correct |
36 ms |
16328 KB |
Output is correct |
10 |
Correct |
32 ms |
16468 KB |
Output is correct |
11 |
Correct |
36 ms |
16332 KB |
Output is correct |
12 |
Correct |
34 ms |
16456 KB |
Output is correct |
13 |
Correct |
34 ms |
16452 KB |
Output is correct |
14 |
Correct |
34 ms |
16276 KB |
Output is correct |
15 |
Correct |
34 ms |
16460 KB |
Output is correct |
16 |
Correct |
31 ms |
16496 KB |
Output is correct |
17 |
Correct |
35 ms |
16188 KB |
Output is correct |
18 |
Correct |
33 ms |
16132 KB |
Output is correct |
19 |
Correct |
28 ms |
16204 KB |
Output is correct |
20 |
Correct |
32 ms |
16196 KB |
Output is correct |
21 |
Correct |
28 ms |
16188 KB |
Output is correct |
22 |
Correct |
28 ms |
16212 KB |
Output is correct |
23 |
Correct |
24 ms |
13648 KB |
Output is correct |
24 |
Correct |
34 ms |
13500 KB |
Output is correct |
25 |
Correct |
30 ms |
14068 KB |
Output is correct |
26 |
Correct |
27 ms |
14156 KB |
Output is correct |
27 |
Correct |
38 ms |
15028 KB |
Output is correct |
28 |
Correct |
28 ms |
15100 KB |
Output is correct |
29 |
Correct |
31 ms |
14960 KB |
Output is correct |
30 |
Correct |
31 ms |
15052 KB |
Output is correct |
31 |
Correct |
34 ms |
13724 KB |
Output is correct |
32 |
Correct |
24 ms |
13724 KB |
Output is correct |
33 |
Correct |
26 ms |
14160 KB |
Output is correct |
34 |
Correct |
28 ms |
14200 KB |
Output is correct |
35 |
Correct |
27 ms |
14784 KB |
Output is correct |
36 |
Correct |
32 ms |
14908 KB |
Output is correct |
37 |
Correct |
35 ms |
14908 KB |
Output is correct |
38 |
Correct |
30 ms |
14956 KB |
Output is correct |
39 |
Correct |
32 ms |
14808 KB |
Output is correct |
40 |
Correct |
34 ms |
14648 KB |
Output is correct |
41 |
Correct |
35 ms |
15728 KB |
Output is correct |
42 |
Correct |
37 ms |
15480 KB |
Output is correct |
43 |
Correct |
30 ms |
15440 KB |
Output is correct |
44 |
Correct |
36 ms |
15492 KB |
Output is correct |
45 |
Correct |
32 ms |
15580 KB |
Output is correct |
46 |
Correct |
33 ms |
15428 KB |
Output is correct |
47 |
Correct |
36 ms |
14848 KB |
Output is correct |
48 |
Correct |
37 ms |
14576 KB |
Output is correct |
49 |
Correct |
28 ms |
14600 KB |
Output is correct |
50 |
Correct |
27 ms |
14648 KB |
Output is correct |
51 |
Correct |
26 ms |
14148 KB |
Output is correct |
52 |
Correct |
38 ms |
14060 KB |
Output is correct |
53 |
Correct |
33 ms |
13968 KB |
Output is correct |
54 |
Correct |
28 ms |
14040 KB |
Output is correct |
55 |
Correct |
30 ms |
14040 KB |
Output is correct |
56 |
Correct |
28 ms |
14116 KB |
Output is correct |
57 |
Correct |
26 ms |
14108 KB |
Output is correct |
58 |
Correct |
30 ms |
14076 KB |
Output is correct |
59 |
Correct |
26 ms |
13896 KB |
Output is correct |
60 |
Correct |
27 ms |
13928 KB |
Output is correct |