#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;
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;
if(A == 3){
int active_cnt = 0, active_guy = -1;
rep(i,3){
if(y[i]){
active_cnt++;
active_guy = i;
}
}
if(active_cnt == 1) return active_guy;
int good = -1;
rep(i,3){
if(y[i] and y[(i+1)%3]){
good = i;
}
}
return 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;
}
move_num++;
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
17664 KB |
Output is correct |
2 |
Correct |
1 ms |
3608 KB |
Output is correct |
3 |
Correct |
25 ms |
17024 KB |
Output is correct |
4 |
Correct |
34 ms |
18464 KB |
Output is correct |
5 |
Correct |
35 ms |
18424 KB |
Output is correct |
6 |
Correct |
31 ms |
17748 KB |
Output is correct |
7 |
Correct |
33 ms |
17792 KB |
Output is correct |
8 |
Correct |
34 ms |
18472 KB |
Output is correct |
9 |
Correct |
33 ms |
18328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
17664 KB |
Output is correct |
2 |
Correct |
1 ms |
3608 KB |
Output is correct |
3 |
Correct |
25 ms |
17024 KB |
Output is correct |
4 |
Correct |
34 ms |
18464 KB |
Output is correct |
5 |
Correct |
35 ms |
18424 KB |
Output is correct |
6 |
Correct |
31 ms |
17748 KB |
Output is correct |
7 |
Correct |
33 ms |
17792 KB |
Output is correct |
8 |
Correct |
34 ms |
18472 KB |
Output is correct |
9 |
Correct |
33 ms |
18328 KB |
Output is correct |
10 |
Incorrect |
25 ms |
15696 KB |
Wrong Answer [6] |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
15080 KB |
Output is correct |
2 |
Correct |
1 ms |
3620 KB |
Output is correct |
3 |
Correct |
27 ms |
14556 KB |
Output is correct |
4 |
Correct |
33 ms |
16300 KB |
Output is correct |
5 |
Correct |
35 ms |
16284 KB |
Output is correct |
6 |
Correct |
27 ms |
15100 KB |
Output is correct |
7 |
Correct |
27 ms |
15212 KB |
Output is correct |
8 |
Correct |
37 ms |
15900 KB |
Output is correct |
9 |
Correct |
39 ms |
15776 KB |
Output is correct |
10 |
Correct |
41 ms |
15580 KB |
Output is correct |
11 |
Correct |
36 ms |
15536 KB |
Output is correct |
12 |
Correct |
34 ms |
15700 KB |
Output is correct |
13 |
Correct |
27 ms |
15600 KB |
Output is correct |
14 |
Correct |
38 ms |
15812 KB |
Output is correct |
15 |
Correct |
44 ms |
15784 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
15080 KB |
Output is correct |
2 |
Correct |
1 ms |
3620 KB |
Output is correct |
3 |
Correct |
27 ms |
14556 KB |
Output is correct |
4 |
Correct |
33 ms |
16300 KB |
Output is correct |
5 |
Correct |
35 ms |
16284 KB |
Output is correct |
6 |
Correct |
27 ms |
15100 KB |
Output is correct |
7 |
Correct |
27 ms |
15212 KB |
Output is correct |
8 |
Correct |
37 ms |
15900 KB |
Output is correct |
9 |
Correct |
39 ms |
15776 KB |
Output is correct |
10 |
Correct |
41 ms |
15580 KB |
Output is correct |
11 |
Correct |
36 ms |
15536 KB |
Output is correct |
12 |
Correct |
34 ms |
15700 KB |
Output is correct |
13 |
Correct |
27 ms |
15600 KB |
Output is correct |
14 |
Correct |
38 ms |
15812 KB |
Output is correct |
15 |
Correct |
44 ms |
15784 KB |
Output is correct |
16 |
Incorrect |
23 ms |
13208 KB |
Wrong Answer [6] |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
3360 KB |
Output is correct |
2 |
Correct |
1 ms |
3100 KB |
Output is correct |
3 |
Correct |
2 ms |
3344 KB |
Output is correct |
4 |
Correct |
2 ms |
3352 KB |
Output is correct |
5 |
Correct |
2 ms |
3352 KB |
Output is correct |
6 |
Correct |
2 ms |
3352 KB |
Output is correct |
7 |
Correct |
3 ms |
3352 KB |
Output is correct |
8 |
Correct |
2 ms |
3352 KB |
Output is correct |
9 |
Correct |
2 ms |
3348 KB |
Output is correct |
10 |
Correct |
2 ms |
3352 KB |
Output is correct |
11 |
Correct |
2 ms |
3360 KB |
Output is correct |
12 |
Correct |
2 ms |
3352 KB |
Output is correct |
13 |
Correct |
2 ms |
3360 KB |
Output is correct |
14 |
Correct |
2 ms |
3352 KB |
Output is correct |
15 |
Correct |
2 ms |
3344 KB |
Output is correct |
16 |
Correct |
2 ms |
3352 KB |
Output is correct |
17 |
Correct |
2 ms |
3344 KB |
Output is correct |
18 |
Correct |
2 ms |
3352 KB |
Output is correct |
19 |
Correct |
3 ms |
3344 KB |
Output is correct |
20 |
Correct |
3 ms |
3352 KB |
Output is correct |
21 |
Correct |
2 ms |
3356 KB |
Output is correct |
22 |
Correct |
3 ms |
3352 KB |
Output is correct |
23 |
Correct |
2 ms |
3352 KB |
Output is correct |
24 |
Correct |
2 ms |
3360 KB |
Output is correct |
25 |
Correct |
2 ms |
3344 KB |
Output is correct |
26 |
Correct |
3 ms |
3356 KB |
Output is correct |
27 |
Correct |
2 ms |
3340 KB |
Output is correct |
28 |
Correct |
3 ms |
3360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
13240 KB |
Output is correct |
2 |
Correct |
35 ms |
14224 KB |
Output is correct |
3 |
Correct |
1 ms |
3092 KB |
Output is correct |
4 |
Correct |
22 ms |
12944 KB |
Output is correct |
5 |
Correct |
44 ms |
15996 KB |
Output is correct |
6 |
Correct |
33 ms |
15904 KB |
Output is correct |
7 |
Correct |
27 ms |
14968 KB |
Output is correct |
8 |
Correct |
27 ms |
14960 KB |
Output is correct |
9 |
Correct |
31 ms |
16044 KB |
Output is correct |
10 |
Correct |
31 ms |
15988 KB |
Output is correct |
11 |
Correct |
34 ms |
15980 KB |
Output is correct |
12 |
Correct |
31 ms |
16028 KB |
Output is correct |
13 |
Correct |
45 ms |
16008 KB |
Output is correct |
14 |
Correct |
30 ms |
16020 KB |
Output is correct |
15 |
Correct |
43 ms |
15992 KB |
Output is correct |
16 |
Correct |
36 ms |
15908 KB |
Output is correct |
17 |
Correct |
36 ms |
15524 KB |
Output is correct |
18 |
Correct |
38 ms |
15720 KB |
Output is correct |
19 |
Correct |
35 ms |
15932 KB |
Output is correct |
20 |
Correct |
36 ms |
15692 KB |
Output is correct |
21 |
Correct |
33 ms |
15500 KB |
Output is correct |
22 |
Correct |
32 ms |
15676 KB |
Output is correct |
23 |
Correct |
27 ms |
13248 KB |
Output is correct |
24 |
Correct |
28 ms |
13132 KB |
Output is correct |
25 |
Correct |
31 ms |
13700 KB |
Output is correct |
26 |
Correct |
33 ms |
13696 KB |
Output is correct |
27 |
Correct |
33 ms |
14656 KB |
Output is correct |
28 |
Correct |
43 ms |
14528 KB |
Output is correct |
29 |
Correct |
30 ms |
14628 KB |
Output is correct |
30 |
Correct |
27 ms |
14704 KB |
Output is correct |
31 |
Correct |
36 ms |
13244 KB |
Output is correct |
32 |
Correct |
25 ms |
13336 KB |
Output is correct |
33 |
Correct |
32 ms |
13492 KB |
Output is correct |
34 |
Correct |
27 ms |
13500 KB |
Output is correct |
35 |
Correct |
32 ms |
14396 KB |
Output is correct |
36 |
Correct |
28 ms |
14544 KB |
Output is correct |
37 |
Correct |
37 ms |
14704 KB |
Output is correct |
38 |
Correct |
34 ms |
14320 KB |
Output is correct |
39 |
Correct |
31 ms |
14408 KB |
Output is correct |
40 |
Correct |
28 ms |
14424 KB |
Output is correct |
41 |
Correct |
30 ms |
14960 KB |
Output is correct |
42 |
Correct |
33 ms |
14964 KB |
Output is correct |
43 |
Correct |
36 ms |
15004 KB |
Output is correct |
44 |
Correct |
35 ms |
14964 KB |
Output is correct |
45 |
Correct |
34 ms |
14956 KB |
Output is correct |
46 |
Correct |
30 ms |
14964 KB |
Output is correct |
47 |
Correct |
33 ms |
14612 KB |
Output is correct |
48 |
Correct |
28 ms |
14440 KB |
Output is correct |
49 |
Correct |
27 ms |
14236 KB |
Output is correct |
50 |
Correct |
33 ms |
14052 KB |
Output is correct |
51 |
Correct |
36 ms |
13668 KB |
Output is correct |
52 |
Correct |
37 ms |
13464 KB |
Output is correct |
53 |
Correct |
36 ms |
13532 KB |
Output is correct |
54 |
Correct |
24 ms |
13400 KB |
Output is correct |
55 |
Correct |
25 ms |
13688 KB |
Output is correct |
56 |
Correct |
28 ms |
13688 KB |
Output is correct |
57 |
Correct |
29 ms |
13600 KB |
Output is correct |
58 |
Correct |
25 ms |
13640 KB |
Output is correct |
59 |
Correct |
27 ms |
13300 KB |
Output is correct |
60 |
Correct |
26 ms |
13500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
13264 KB |
Output is correct |
2 |
Correct |
32 ms |
14344 KB |
Output is correct |
3 |
Correct |
1 ms |
3100 KB |
Output is correct |
4 |
Correct |
20 ms |
12912 KB |
Output is correct |
5 |
Correct |
34 ms |
15996 KB |
Output is correct |
6 |
Correct |
31 ms |
15976 KB |
Output is correct |
7 |
Correct |
27 ms |
14892 KB |
Output is correct |
8 |
Correct |
33 ms |
14988 KB |
Output is correct |
9 |
Correct |
37 ms |
15780 KB |
Output is correct |
10 |
Correct |
37 ms |
15980 KB |
Output is correct |
11 |
Correct |
44 ms |
15824 KB |
Output is correct |
12 |
Correct |
38 ms |
15908 KB |
Output is correct |
13 |
Correct |
36 ms |
15952 KB |
Output is correct |
14 |
Correct |
31 ms |
16020 KB |
Output is correct |
15 |
Correct |
30 ms |
15980 KB |
Output is correct |
16 |
Correct |
36 ms |
15916 KB |
Output is correct |
17 |
Correct |
34 ms |
15476 KB |
Output is correct |
18 |
Correct |
39 ms |
15664 KB |
Output is correct |
19 |
Correct |
38 ms |
15648 KB |
Output is correct |
20 |
Correct |
37 ms |
15364 KB |
Output is correct |
21 |
Correct |
33 ms |
15748 KB |
Output is correct |
22 |
Correct |
35 ms |
15732 KB |
Output is correct |
23 |
Correct |
25 ms |
13256 KB |
Output is correct |
24 |
Correct |
31 ms |
13188 KB |
Output is correct |
25 |
Correct |
27 ms |
13556 KB |
Output is correct |
26 |
Correct |
28 ms |
13800 KB |
Output is correct |
27 |
Correct |
38 ms |
14760 KB |
Output is correct |
28 |
Correct |
33 ms |
14640 KB |
Output is correct |
29 |
Correct |
36 ms |
14668 KB |
Output is correct |
30 |
Correct |
33 ms |
14704 KB |
Output is correct |
31 |
Correct |
30 ms |
13176 KB |
Output is correct |
32 |
Correct |
25 ms |
13176 KB |
Output is correct |
33 |
Correct |
28 ms |
13688 KB |
Output is correct |
34 |
Correct |
28 ms |
13764 KB |
Output is correct |
35 |
Correct |
30 ms |
14456 KB |
Output is correct |
36 |
Correct |
33 ms |
14448 KB |
Output is correct |
37 |
Correct |
30 ms |
14456 KB |
Output is correct |
38 |
Correct |
27 ms |
14428 KB |
Output is correct |
39 |
Correct |
27 ms |
14448 KB |
Output is correct |
40 |
Correct |
32 ms |
14460 KB |
Output is correct |
41 |
Correct |
28 ms |
14968 KB |
Output is correct |
42 |
Correct |
30 ms |
14972 KB |
Output is correct |
43 |
Correct |
30 ms |
15000 KB |
Output is correct |
44 |
Correct |
30 ms |
14960 KB |
Output is correct |
45 |
Correct |
36 ms |
14952 KB |
Output is correct |
46 |
Correct |
36 ms |
14924 KB |
Output is correct |
47 |
Correct |
32 ms |
14448 KB |
Output is correct |
48 |
Correct |
26 ms |
14532 KB |
Output is correct |
49 |
Correct |
26 ms |
14188 KB |
Output is correct |
50 |
Correct |
30 ms |
14708 KB |
Output is correct |
51 |
Correct |
26 ms |
13696 KB |
Output is correct |
52 |
Correct |
25 ms |
13688 KB |
Output is correct |
53 |
Correct |
25 ms |
13476 KB |
Output is correct |
54 |
Correct |
26 ms |
13556 KB |
Output is correct |
55 |
Correct |
30 ms |
13608 KB |
Output is correct |
56 |
Correct |
25 ms |
13688 KB |
Output is correct |
57 |
Correct |
25 ms |
13696 KB |
Output is correct |
58 |
Correct |
27 ms |
13680 KB |
Output is correct |
59 |
Correct |
25 ms |
13504 KB |
Output is correct |
60 |
Correct |
26 ms |
13428 KB |
Output is correct |