#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);
}
}
}
} // 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;
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,-1);
dfs1(0,-1,1,-1);
debug(val);
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 = A_;
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;
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;
}
Compilation message
Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:59:18: warning: statement has no effect [-Wunused-value]
59 | #define debug(x) 42
| ^~
Anthony.cpp:161:5: note: in expansion of macro 'debug'
161 | debug(val);
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
17996 KB |
Output is correct |
2 |
Correct |
1 ms |
3088 KB |
Output is correct |
3 |
Correct |
27 ms |
16576 KB |
Output is correct |
4 |
Correct |
39 ms |
19660 KB |
Output is correct |
5 |
Incorrect |
38 ms |
19632 KB |
Wrong Answer [6] |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
17996 KB |
Output is correct |
2 |
Correct |
1 ms |
3088 KB |
Output is correct |
3 |
Correct |
27 ms |
16576 KB |
Output is correct |
4 |
Correct |
39 ms |
19660 KB |
Output is correct |
5 |
Incorrect |
38 ms |
19632 KB |
Wrong Answer [6] |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
15772 KB |
Output is correct |
2 |
Correct |
1 ms |
3084 KB |
Output is correct |
3 |
Correct |
26 ms |
14500 KB |
Output is correct |
4 |
Correct |
40 ms |
17544 KB |
Output is correct |
5 |
Incorrect |
47 ms |
17336 KB |
Wrong Answer [6] |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
15772 KB |
Output is correct |
2 |
Correct |
1 ms |
3084 KB |
Output is correct |
3 |
Correct |
26 ms |
14500 KB |
Output is correct |
4 |
Correct |
40 ms |
17544 KB |
Output is correct |
5 |
Incorrect |
47 ms |
17336 KB |
Wrong Answer [6] |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3356 KB |
Output is correct |
2 |
Correct |
1 ms |
3088 KB |
Output is correct |
3 |
Correct |
2 ms |
3352 KB |
Output is correct |
4 |
Correct |
2 ms |
3372 KB |
Output is correct |
5 |
Correct |
2 ms |
3352 KB |
Output is correct |
6 |
Correct |
2 ms |
3352 KB |
Output is correct |
7 |
Correct |
2 ms |
3360 KB |
Output is correct |
8 |
Correct |
2 ms |
3352 KB |
Output is correct |
9 |
Correct |
2 ms |
3344 KB |
Output is correct |
10 |
Correct |
2 ms |
3524 KB |
Output is correct |
11 |
Correct |
2 ms |
3344 KB |
Output is correct |
12 |
Correct |
2 ms |
3360 KB |
Output is correct |
13 |
Correct |
2 ms |
3352 KB |
Output is correct |
14 |
Correct |
2 ms |
3312 KB |
Output is correct |
15 |
Correct |
2 ms |
3352 KB |
Output is correct |
16 |
Correct |
2 ms |
3348 KB |
Output is correct |
17 |
Correct |
2 ms |
3352 KB |
Output is correct |
18 |
Correct |
2 ms |
3356 KB |
Output is correct |
19 |
Correct |
2 ms |
3352 KB |
Output is correct |
20 |
Correct |
2 ms |
3360 KB |
Output is correct |
21 |
Correct |
3 ms |
3352 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 |
3356 KB |
Output is correct |
25 |
Correct |
2 ms |
3352 KB |
Output is correct |
26 |
Correct |
2 ms |
3348 KB |
Output is correct |
27 |
Correct |
2 ms |
3348 KB |
Output is correct |
28 |
Correct |
3 ms |
3352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
13148 KB |
Output is correct |
2 |
Correct |
33 ms |
14332 KB |
Output is correct |
3 |
Correct |
1 ms |
3088 KB |
Output is correct |
4 |
Correct |
27 ms |
12944 KB |
Output is correct |
5 |
Correct |
34 ms |
15944 KB |
Output is correct |
6 |
Correct |
40 ms |
15876 KB |
Output is correct |
7 |
Correct |
32 ms |
14968 KB |
Output is correct |
8 |
Correct |
28 ms |
15100 KB |
Output is correct |
9 |
Correct |
44 ms |
15696 KB |
Output is correct |
10 |
Correct |
37 ms |
15972 KB |
Output is correct |
11 |
Correct |
51 ms |
15868 KB |
Output is correct |
12 |
Correct |
41 ms |
15944 KB |
Output is correct |
13 |
Correct |
40 ms |
15996 KB |
Output is correct |
14 |
Correct |
34 ms |
15960 KB |
Output is correct |
15 |
Correct |
38 ms |
15984 KB |
Output is correct |
16 |
Correct |
43 ms |
15872 KB |
Output is correct |
17 |
Correct |
35 ms |
15788 KB |
Output is correct |
18 |
Correct |
38 ms |
15672 KB |
Output is correct |
19 |
Correct |
33 ms |
15688 KB |
Output is correct |
20 |
Correct |
37 ms |
15632 KB |
Output is correct |
21 |
Correct |
44 ms |
15632 KB |
Output is correct |
22 |
Correct |
31 ms |
15740 KB |
Output is correct |
23 |
Correct |
34 ms |
13244 KB |
Output is correct |
24 |
Correct |
31 ms |
13132 KB |
Output is correct |
25 |
Correct |
28 ms |
13552 KB |
Output is correct |
26 |
Correct |
31 ms |
13644 KB |
Output is correct |
27 |
Correct |
33 ms |
14464 KB |
Output is correct |
28 |
Correct |
32 ms |
14556 KB |
Output is correct |
29 |
Correct |
36 ms |
14616 KB |
Output is correct |
30 |
Correct |
30 ms |
14448 KB |
Output is correct |
31 |
Correct |
31 ms |
13172 KB |
Output is correct |
32 |
Correct |
26 ms |
13260 KB |
Output is correct |
33 |
Correct |
30 ms |
13512 KB |
Output is correct |
34 |
Correct |
27 ms |
13744 KB |
Output is correct |
35 |
Correct |
41 ms |
14460 KB |
Output is correct |
36 |
Correct |
34 ms |
14564 KB |
Output is correct |
37 |
Correct |
35 ms |
14324 KB |
Output is correct |
38 |
Correct |
33 ms |
14580 KB |
Output is correct |
39 |
Correct |
31 ms |
14600 KB |
Output is correct |
40 |
Correct |
32 ms |
14492 KB |
Output is correct |
41 |
Correct |
36 ms |
15212 KB |
Output is correct |
42 |
Correct |
36 ms |
14996 KB |
Output is correct |
43 |
Correct |
35 ms |
15092 KB |
Output is correct |
44 |
Correct |
33 ms |
14956 KB |
Output is correct |
45 |
Correct |
31 ms |
14960 KB |
Output is correct |
46 |
Correct |
31 ms |
14988 KB |
Output is correct |
47 |
Correct |
28 ms |
14252 KB |
Output is correct |
48 |
Correct |
28 ms |
14380 KB |
Output is correct |
49 |
Correct |
33 ms |
14388 KB |
Output is correct |
50 |
Correct |
31 ms |
14496 KB |
Output is correct |
51 |
Correct |
31 ms |
13604 KB |
Output is correct |
52 |
Correct |
27 ms |
13692 KB |
Output is correct |
53 |
Correct |
30 ms |
13476 KB |
Output is correct |
54 |
Correct |
32 ms |
13496 KB |
Output is correct |
55 |
Correct |
26 ms |
13436 KB |
Output is correct |
56 |
Correct |
27 ms |
13324 KB |
Output is correct |
57 |
Correct |
32 ms |
13496 KB |
Output is correct |
58 |
Correct |
30 ms |
13284 KB |
Output is correct |
59 |
Correct |
34 ms |
13384 KB |
Output is correct |
60 |
Correct |
36 ms |
13396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
13172 KB |
Output is correct |
2 |
Correct |
35 ms |
14276 KB |
Output is correct |
3 |
Correct |
1 ms |
3092 KB |
Output is correct |
4 |
Correct |
23 ms |
12988 KB |
Output is correct |
5 |
Correct |
37 ms |
15988 KB |
Output is correct |
6 |
Correct |
49 ms |
15796 KB |
Output is correct |
7 |
Correct |
28 ms |
15008 KB |
Output is correct |
8 |
Correct |
27 ms |
15040 KB |
Output is correct |
9 |
Correct |
33 ms |
16456 KB |
Output is correct |
10 |
Correct |
39 ms |
16308 KB |
Output is correct |
11 |
Correct |
41 ms |
16200 KB |
Output is correct |
12 |
Correct |
33 ms |
16400 KB |
Output is correct |
13 |
Correct |
39 ms |
16424 KB |
Output is correct |
14 |
Correct |
33 ms |
16256 KB |
Output is correct |
15 |
Correct |
31 ms |
16460 KB |
Output is correct |
16 |
Correct |
33 ms |
16468 KB |
Output is correct |
17 |
Correct |
34 ms |
16012 KB |
Output is correct |
18 |
Correct |
30 ms |
16192 KB |
Output is correct |
19 |
Correct |
31 ms |
16032 KB |
Output is correct |
20 |
Correct |
31 ms |
16032 KB |
Output is correct |
21 |
Correct |
30 ms |
16244 KB |
Output is correct |
22 |
Correct |
30 ms |
16200 KB |
Output is correct |
23 |
Correct |
25 ms |
13624 KB |
Output is correct |
24 |
Correct |
28 ms |
13600 KB |
Output is correct |
25 |
Correct |
26 ms |
14156 KB |
Output is correct |
26 |
Correct |
27 ms |
14148 KB |
Output is correct |
27 |
Correct |
30 ms |
15172 KB |
Output is correct |
28 |
Correct |
27 ms |
15180 KB |
Output is correct |
29 |
Correct |
28 ms |
14972 KB |
Output is correct |
30 |
Correct |
35 ms |
14924 KB |
Output is correct |
31 |
Correct |
26 ms |
13640 KB |
Output is correct |
32 |
Correct |
26 ms |
13792 KB |
Output is correct |
33 |
Correct |
26 ms |
13980 KB |
Output is correct |
34 |
Correct |
27 ms |
14288 KB |
Output is correct |
35 |
Correct |
27 ms |
14856 KB |
Output is correct |
36 |
Correct |
31 ms |
14900 KB |
Output is correct |
37 |
Correct |
36 ms |
14840 KB |
Output is correct |
38 |
Correct |
27 ms |
14864 KB |
Output is correct |
39 |
Correct |
30 ms |
15024 KB |
Output is correct |
40 |
Correct |
28 ms |
14840 KB |
Output is correct |
41 |
Correct |
32 ms |
15440 KB |
Output is correct |
42 |
Correct |
34 ms |
15504 KB |
Output is correct |
43 |
Correct |
30 ms |
15536 KB |
Output is correct |
44 |
Correct |
33 ms |
15416 KB |
Output is correct |
45 |
Correct |
36 ms |
15368 KB |
Output is correct |
46 |
Correct |
34 ms |
15496 KB |
Output is correct |
47 |
Correct |
27 ms |
14664 KB |
Output is correct |
48 |
Correct |
27 ms |
14668 KB |
Output is correct |
49 |
Correct |
30 ms |
14636 KB |
Output is correct |
50 |
Correct |
31 ms |
14620 KB |
Output is correct |
51 |
Correct |
34 ms |
14088 KB |
Output is correct |
52 |
Correct |
27 ms |
14076 KB |
Output is correct |
53 |
Correct |
26 ms |
14156 KB |
Output is correct |
54 |
Correct |
28 ms |
14076 KB |
Output is correct |
55 |
Correct |
26 ms |
14152 KB |
Output is correct |
56 |
Correct |
26 ms |
14132 KB |
Output is correct |
57 |
Correct |
28 ms |
14144 KB |
Output is correct |
58 |
Correct |
28 ms |
14160 KB |
Output is correct |
59 |
Correct |
29 ms |
13852 KB |
Output is correct |
60 |
Correct |
26 ms |
14052 KB |
Output is correct |