# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
212281 |
2020-03-22T16:32:45 Z |
Evirir |
Stray Cat (JOI20_stray) |
C++17 |
|
103 ms |
22400 KB |
#include "Anthony.h"
#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;
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define F first
#define S second
#define INF ll(1e18)
#define MOD 998244353
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#define MAXN 200005
namespace ant{
string s="010110";
bool DEBUG=0;
int n,m;
vii adj[MAXN];
}
using namespace ant;
vector<int> ans;
bool vst[MAXN];
int dep[MAXN];
void bfs1()
{
mset(vst,0); mset(dep,0);
queue<int> q;
q.push(0);
while(!q.empty()){
int u=q.front(); q.pop();
for(ii tmp: adj[u]){
int v=tmp.F;
if(vst[v]) continue;
dep[v]=dep[u]+1;
vst[v]=1;
q.push(v);
}
}
}
void bfs()
{
mset(vst,0);
queue<ii> q;
q.push({0,0});
vst[0]=1;
while(!q.empty()){
int u=q.front().F, c=q.front().S; q.pop();
for(ii tmp: adj[u]){
int v=tmp.F, id=tmp.S;
if(vst[v]){
if(ans[id]==-1){
if(dep[u]>dep[v]) ans[id]=(c-1)%3;
else ans[id]=c;
if(DEBUG) cout<<"c="<<c<<" Edge "<<u<<"-"<<v<<": "<<ans[id]<<" dep[u]="<<dep[u]<<" dep[v]="<<dep[v]<<" u="<<u<<" v="<<v<<'\n';
}
}
else{
if(ans[id]==-1){
ans[id]=c;
if(DEBUG) cout<<"Edge "<<u<<"-"<<v<<": "<<ans[id]<<'\n';
}
vst[v]=1;
q.push({v,(c+1)%3});
}
}
}
}
void dfs(int u,int p,int c,int pos)
{
if(adj[u].size()==2)
{
for(ii tmp: adj[u]){
int v=tmp.F, id=tmp.S;
if(v==p) continue;
ans[id]=s[pos]-'0';
dfs(v,u,ans[id]^1,(pos+1)%6);
}
return;
}
for(ii tmp: adj[u]){
int v=tmp.F, id=tmp.S;
if(v==p) continue;
ans[id]=c;
dfs(v,u,c^1,c+1);
}
}
vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V)
{
ans.resize(m,-1);
mset(vst,0);
forn(i,0,m){
adj[U[i]].pb({V[i],i});
adj[V[i]].pb({U[i],i});
}
if(A>=3){
bfs1(); bfs();
}
else dfs(0,-1,0,0);
return ans;
}
#include "Catherine.h"
#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;
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define F first
#define S second
#define INF ll(1e18)
#define MOD 998244353
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#define MAXN 200005
namespace cat{
int A,B;
bool DEBUG=0;
int Prev=-1;
string s;
}
using namespace cat;
int mode=0;
string banarr[4]={"0010","0101","01100","1100"};
unordered_set<string> ban;
void Init(int _A, int _B)
{
A=_A; B=_B; mode=0; Prev=-1; s="";
ban.clear(); ban.insert(banarr,banarr+4);
}
int cmp(int a,int b){
if(a>b) swap(a,b);
if(a==0 && b==2) return 2;
return a;
}
int Move1(vector<int> &v1)
{
vector<int> v;
forn(i,0,3) if(v1[i]) v.pb(i);
if(DEBUG){
cout<<"Possible moves: ";
forn(i,0,v.size()) cout<<v[i]<<" ";
cout<<'\n';
}
assert(v.size()==1 || v.size()==2);
if(v.size()==1) return v[0];
return cmp(v[0],v[1]);
}
int Move2(vector<int> &v)
{
//first 3 steps, dunno direction
if(!mode)
{
//first step
if(Prev==-1)
{
//leaf node
if(v[0]+v[1]==1)
{
if(DEBUG) cout<<"1st step: leaf node\n";
mode=1;
Prev=(v[0]>0?0:1);
return Prev;
}
//non-line
else if(v[0]+v[1]>=3)
{
if(DEBUG) cout<<"1st step: non-line\n";
assert(v[0]==1 || v[1]==1);
mode=1;
if(v[0]==1){
Prev=0;
return Prev;
}
else{
Prev=1;
return Prev;
}
}
//line graph
else
{
if(DEBUG) cout<<"1st step: line graph\n";
if(v[0]==2 && v[1]==0){
s+="00";
Prev=0;
return 0;
}
if(v[0]==1 && v[1]==1){
s+="01";
Prev=1;
return 1;
}
if(v[0]==0 && v[1]==2){
s+="11";
Prev=1;
return 1;
}
}
cout<<"First step fail\n";
assert(0);
}
//first step end
//second/third step
else
{
//leaf node
if(v[0]+v[1]==0)
{
if(DEBUG) cout<<"2/3 step: leaf\n";
mode=1;
Prev=s.back()-'0';
s.pop_back();
return -1;
}
//non-line: added v
else if(v[0]+v[1]>=2)
{
if(DEBUG) cout<<"2/3 step: non-line\n";
if(Prev==0) v[0]++;
else v[1]++;
assert(v[0]==1 || v[1]==1);
mode=1;
if(v[0]==1){
if(Prev==0) return -1;
Prev=0;
return Prev;
}
else{
if(Prev==1) return -1;
Prev=1;
return Prev;
}
}
//line graph
else //v[0]==1 || v[1]==1
{
if(DEBUG) cout<<"2/3 step: line\n";
//third step, decide
if(s.size()==4){
mode=1;
if(DEBUG) cout<<"s="<<s<<'\n';
if(ban.find(s)!=ban.end()){
Prev=s.back()-'0';
s.pop_back();
return -1;
}
else{
if(v[0]) s+='0';
else s+='1';
if(DEBUG) cout<<"s="<<s<<'\n';
if(ban.find(s)!=ban.end()){
//Prev remains
s.pop_back();
return -1;
}
else{
Prev=(v[0]?0:1);
return Prev;
}
}
}
//second step
if(v[0]==1 && v[1]==0){
s+="0";
Prev=0;
return 0;
}
if(v[0]==0 && v[1]==1){
s+="1";
Prev=1;
return 1;
}
}
cout<<"Second/third step fail\n";
assert(0);
}
//second/third step end
}
//direction confirmed
else
{
assert(v[0]+v[1]!=0);
//line graph
if(v[0]+v[1]==1)
{
if(v[0]){
Prev=0; return 0;
}
else{
Prev=1; return 1;
}
}
//non-line
else
{
v[Prev]++;
if(DEBUG) cout<<"Prev="<<Prev<<" v[0]="<<v[0]<<" v[1]="<<v[1]<<'\n';
if(v[0]==1){
Prev=0; return 0;
}
else{
Prev=1; return 1;
}
}
assert(0);
return 222;
}
return 333;
}
int Move(vector<int> v)
{
if(A>=3) return Move1(v);
return Move2(v);
}
Compilation message
Catherine.cpp: In function 'int Move1(std::vector<int>&)':
Catherine.cpp:11:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define forn(i,a,b) for(int i=a;i<b;i++)
Catherine.cpp:61:8:
forn(i,0,v.size()) cout<<v[i]<<" ";
~~~~~~~~~~~~
Catherine.cpp:61:3: note: in expansion of macro 'forn'
forn(i,0,v.size()) cout<<v[i]<<" ";
^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
21100 KB |
Output is correct |
2 |
Correct |
13 ms |
12032 KB |
Output is correct |
3 |
Correct |
59 ms |
20424 KB |
Output is correct |
4 |
Correct |
84 ms |
22400 KB |
Output is correct |
5 |
Correct |
86 ms |
22352 KB |
Output is correct |
6 |
Correct |
67 ms |
21096 KB |
Output is correct |
7 |
Correct |
82 ms |
21060 KB |
Output is correct |
8 |
Correct |
93 ms |
21800 KB |
Output is correct |
9 |
Correct |
93 ms |
21828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
21100 KB |
Output is correct |
2 |
Correct |
13 ms |
12032 KB |
Output is correct |
3 |
Correct |
59 ms |
20424 KB |
Output is correct |
4 |
Correct |
84 ms |
22400 KB |
Output is correct |
5 |
Correct |
86 ms |
22352 KB |
Output is correct |
6 |
Correct |
67 ms |
21096 KB |
Output is correct |
7 |
Correct |
82 ms |
21060 KB |
Output is correct |
8 |
Correct |
93 ms |
21800 KB |
Output is correct |
9 |
Correct |
93 ms |
21828 KB |
Output is correct |
10 |
Correct |
57 ms |
19048 KB |
Output is correct |
11 |
Correct |
59 ms |
18928 KB |
Output is correct |
12 |
Correct |
64 ms |
19064 KB |
Output is correct |
13 |
Correct |
71 ms |
19004 KB |
Output is correct |
14 |
Correct |
73 ms |
19432 KB |
Output is correct |
15 |
Correct |
68 ms |
19880 KB |
Output is correct |
16 |
Correct |
75 ms |
21856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
18904 KB |
Output is correct |
2 |
Correct |
12 ms |
12032 KB |
Output is correct |
3 |
Correct |
60 ms |
18164 KB |
Output is correct |
4 |
Correct |
83 ms |
20212 KB |
Output is correct |
5 |
Correct |
79 ms |
20192 KB |
Output is correct |
6 |
Correct |
70 ms |
18628 KB |
Output is correct |
7 |
Correct |
68 ms |
18804 KB |
Output is correct |
8 |
Correct |
81 ms |
19364 KB |
Output is correct |
9 |
Correct |
72 ms |
19456 KB |
Output is correct |
10 |
Correct |
72 ms |
19316 KB |
Output is correct |
11 |
Correct |
71 ms |
19204 KB |
Output is correct |
12 |
Correct |
67 ms |
19320 KB |
Output is correct |
13 |
Correct |
71 ms |
19300 KB |
Output is correct |
14 |
Correct |
76 ms |
19460 KB |
Output is correct |
15 |
Correct |
84 ms |
19488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
18904 KB |
Output is correct |
2 |
Correct |
12 ms |
12032 KB |
Output is correct |
3 |
Correct |
60 ms |
18164 KB |
Output is correct |
4 |
Correct |
83 ms |
20212 KB |
Output is correct |
5 |
Correct |
79 ms |
20192 KB |
Output is correct |
6 |
Correct |
70 ms |
18628 KB |
Output is correct |
7 |
Correct |
68 ms |
18804 KB |
Output is correct |
8 |
Correct |
81 ms |
19364 KB |
Output is correct |
9 |
Correct |
72 ms |
19456 KB |
Output is correct |
10 |
Correct |
72 ms |
19316 KB |
Output is correct |
11 |
Correct |
71 ms |
19204 KB |
Output is correct |
12 |
Correct |
67 ms |
19320 KB |
Output is correct |
13 |
Correct |
71 ms |
19300 KB |
Output is correct |
14 |
Correct |
76 ms |
19460 KB |
Output is correct |
15 |
Correct |
84 ms |
19488 KB |
Output is correct |
16 |
Correct |
62 ms |
17272 KB |
Output is correct |
17 |
Correct |
59 ms |
17168 KB |
Output is correct |
18 |
Correct |
64 ms |
17120 KB |
Output is correct |
19 |
Correct |
69 ms |
17116 KB |
Output is correct |
20 |
Correct |
63 ms |
17912 KB |
Output is correct |
21 |
Correct |
58 ms |
17656 KB |
Output is correct |
22 |
Correct |
77 ms |
19692 KB |
Output is correct |
23 |
Correct |
61 ms |
17136 KB |
Output is correct |
24 |
Correct |
59 ms |
17304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
10496 KB |
Output is correct |
2 |
Correct |
13 ms |
10496 KB |
Output is correct |
3 |
Correct |
14 ms |
10496 KB |
Output is correct |
4 |
Correct |
14 ms |
10752 KB |
Output is correct |
5 |
Correct |
14 ms |
10496 KB |
Output is correct |
6 |
Correct |
16 ms |
10752 KB |
Output is correct |
7 |
Correct |
13 ms |
10592 KB |
Output is correct |
8 |
Correct |
13 ms |
10496 KB |
Output is correct |
9 |
Correct |
13 ms |
10496 KB |
Output is correct |
10 |
Correct |
13 ms |
10496 KB |
Output is correct |
11 |
Correct |
14 ms |
10752 KB |
Output is correct |
12 |
Correct |
13 ms |
10496 KB |
Output is correct |
13 |
Correct |
13 ms |
10496 KB |
Output is correct |
14 |
Correct |
13 ms |
10496 KB |
Output is correct |
15 |
Correct |
13 ms |
10496 KB |
Output is correct |
16 |
Correct |
16 ms |
10496 KB |
Output is correct |
17 |
Correct |
13 ms |
10496 KB |
Output is correct |
18 |
Correct |
13 ms |
10448 KB |
Output is correct |
19 |
Correct |
13 ms |
10496 KB |
Output is correct |
20 |
Correct |
13 ms |
10496 KB |
Output is correct |
21 |
Correct |
13 ms |
10496 KB |
Output is correct |
22 |
Correct |
13 ms |
10496 KB |
Output is correct |
23 |
Correct |
13 ms |
10496 KB |
Output is correct |
24 |
Correct |
13 ms |
10496 KB |
Output is correct |
25 |
Correct |
13 ms |
10496 KB |
Output is correct |
26 |
Correct |
13 ms |
10496 KB |
Output is correct |
27 |
Correct |
13 ms |
10496 KB |
Output is correct |
28 |
Correct |
16 ms |
10496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
16312 KB |
Output is correct |
2 |
Correct |
69 ms |
17404 KB |
Output is correct |
3 |
Correct |
13 ms |
10496 KB |
Output is correct |
4 |
Correct |
47 ms |
15800 KB |
Output is correct |
5 |
Correct |
66 ms |
18684 KB |
Output is correct |
6 |
Correct |
86 ms |
18652 KB |
Output is correct |
7 |
Correct |
63 ms |
17804 KB |
Output is correct |
8 |
Correct |
61 ms |
17652 KB |
Output is correct |
9 |
Correct |
81 ms |
18768 KB |
Output is correct |
10 |
Correct |
67 ms |
18640 KB |
Output is correct |
11 |
Correct |
71 ms |
18696 KB |
Output is correct |
12 |
Correct |
77 ms |
18568 KB |
Output is correct |
13 |
Correct |
74 ms |
18780 KB |
Output is correct |
14 |
Correct |
103 ms |
18608 KB |
Output is correct |
15 |
Correct |
83 ms |
18604 KB |
Output is correct |
16 |
Correct |
83 ms |
18636 KB |
Output is correct |
17 |
Correct |
72 ms |
18284 KB |
Output is correct |
18 |
Correct |
65 ms |
18300 KB |
Output is correct |
19 |
Correct |
68 ms |
18380 KB |
Output is correct |
20 |
Correct |
84 ms |
18296 KB |
Output is correct |
21 |
Correct |
87 ms |
18332 KB |
Output is correct |
22 |
Correct |
70 ms |
18292 KB |
Output is correct |
23 |
Correct |
57 ms |
16116 KB |
Output is correct |
24 |
Correct |
66 ms |
16116 KB |
Output is correct |
25 |
Correct |
62 ms |
16564 KB |
Output is correct |
26 |
Correct |
59 ms |
16500 KB |
Output is correct |
27 |
Correct |
62 ms |
17412 KB |
Output is correct |
28 |
Correct |
63 ms |
17568 KB |
Output is correct |
29 |
Correct |
64 ms |
17540 KB |
Output is correct |
30 |
Correct |
64 ms |
17396 KB |
Output is correct |
31 |
Correct |
63 ms |
16252 KB |
Output is correct |
32 |
Correct |
69 ms |
16368 KB |
Output is correct |
33 |
Correct |
67 ms |
16508 KB |
Output is correct |
34 |
Correct |
57 ms |
16500 KB |
Output is correct |
35 |
Correct |
59 ms |
17328 KB |
Output is correct |
36 |
Correct |
66 ms |
17268 KB |
Output is correct |
37 |
Correct |
76 ms |
17356 KB |
Output is correct |
38 |
Correct |
63 ms |
17268 KB |
Output is correct |
39 |
Correct |
68 ms |
17260 KB |
Output is correct |
40 |
Correct |
62 ms |
17228 KB |
Output is correct |
41 |
Correct |
69 ms |
17908 KB |
Output is correct |
42 |
Correct |
64 ms |
17916 KB |
Output is correct |
43 |
Correct |
80 ms |
17828 KB |
Output is correct |
44 |
Correct |
78 ms |
17856 KB |
Output is correct |
45 |
Correct |
75 ms |
17772 KB |
Output is correct |
46 |
Correct |
77 ms |
18020 KB |
Output is correct |
47 |
Correct |
68 ms |
17164 KB |
Output is correct |
48 |
Correct |
73 ms |
17048 KB |
Output is correct |
49 |
Correct |
67 ms |
17148 KB |
Output is correct |
50 |
Correct |
60 ms |
17252 KB |
Output is correct |
51 |
Correct |
57 ms |
16572 KB |
Output is correct |
52 |
Correct |
56 ms |
16508 KB |
Output is correct |
53 |
Correct |
60 ms |
16548 KB |
Output is correct |
54 |
Correct |
61 ms |
16612 KB |
Output is correct |
55 |
Correct |
59 ms |
16636 KB |
Output is correct |
56 |
Correct |
59 ms |
16636 KB |
Output is correct |
57 |
Correct |
63 ms |
16504 KB |
Output is correct |
58 |
Correct |
61 ms |
16652 KB |
Output is correct |
59 |
Correct |
62 ms |
16484 KB |
Output is correct |
60 |
Correct |
67 ms |
16484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
16256 KB |
Output is correct |
2 |
Correct |
87 ms |
17216 KB |
Output is correct |
3 |
Correct |
13 ms |
10496 KB |
Output is correct |
4 |
Correct |
48 ms |
15856 KB |
Output is correct |
5 |
Correct |
89 ms |
18600 KB |
Output is correct |
6 |
Correct |
76 ms |
18804 KB |
Output is correct |
7 |
Correct |
63 ms |
17900 KB |
Output is correct |
8 |
Correct |
65 ms |
17788 KB |
Output is correct |
9 |
Correct |
71 ms |
18484 KB |
Output is correct |
10 |
Correct |
71 ms |
18704 KB |
Output is correct |
11 |
Correct |
70 ms |
18684 KB |
Output is correct |
12 |
Correct |
84 ms |
18632 KB |
Output is correct |
13 |
Correct |
79 ms |
18640 KB |
Output is correct |
14 |
Correct |
80 ms |
18636 KB |
Output is correct |
15 |
Correct |
94 ms |
18636 KB |
Output is correct |
16 |
Correct |
84 ms |
18752 KB |
Output is correct |
17 |
Correct |
84 ms |
18416 KB |
Output is correct |
18 |
Correct |
80 ms |
18396 KB |
Output is correct |
19 |
Correct |
71 ms |
18292 KB |
Output is correct |
20 |
Correct |
67 ms |
18420 KB |
Output is correct |
21 |
Correct |
77 ms |
18284 KB |
Output is correct |
22 |
Correct |
71 ms |
18344 KB |
Output is correct |
23 |
Correct |
56 ms |
16240 KB |
Output is correct |
24 |
Correct |
59 ms |
16108 KB |
Output is correct |
25 |
Correct |
57 ms |
16720 KB |
Output is correct |
26 |
Correct |
55 ms |
16644 KB |
Output is correct |
27 |
Correct |
65 ms |
17476 KB |
Output is correct |
28 |
Correct |
67 ms |
17540 KB |
Output is correct |
29 |
Correct |
61 ms |
17540 KB |
Output is correct |
30 |
Correct |
63 ms |
17532 KB |
Output is correct |
31 |
Correct |
56 ms |
16200 KB |
Output is correct |
32 |
Correct |
54 ms |
16244 KB |
Output is correct |
33 |
Correct |
62 ms |
16628 KB |
Output is correct |
34 |
Correct |
54 ms |
16740 KB |
Output is correct |
35 |
Correct |
72 ms |
17260 KB |
Output is correct |
36 |
Correct |
73 ms |
17388 KB |
Output is correct |
37 |
Correct |
62 ms |
17276 KB |
Output is correct |
38 |
Correct |
94 ms |
17352 KB |
Output is correct |
39 |
Correct |
66 ms |
17248 KB |
Output is correct |
40 |
Correct |
70 ms |
17268 KB |
Output is correct |
41 |
Correct |
74 ms |
18036 KB |
Output is correct |
42 |
Correct |
81 ms |
17812 KB |
Output is correct |
43 |
Correct |
74 ms |
18036 KB |
Output is correct |
44 |
Correct |
70 ms |
17868 KB |
Output is correct |
45 |
Correct |
69 ms |
17876 KB |
Output is correct |
46 |
Correct |
74 ms |
17960 KB |
Output is correct |
47 |
Correct |
75 ms |
17080 KB |
Output is correct |
48 |
Correct |
63 ms |
17132 KB |
Output is correct |
49 |
Correct |
72 ms |
16876 KB |
Output is correct |
50 |
Correct |
60 ms |
17156 KB |
Output is correct |
51 |
Correct |
77 ms |
16532 KB |
Output is correct |
52 |
Correct |
58 ms |
16604 KB |
Output is correct |
53 |
Correct |
55 ms |
16556 KB |
Output is correct |
54 |
Correct |
53 ms |
16636 KB |
Output is correct |
55 |
Correct |
69 ms |
16628 KB |
Output is correct |
56 |
Correct |
57 ms |
16484 KB |
Output is correct |
57 |
Correct |
61 ms |
16716 KB |
Output is correct |
58 |
Correct |
58 ms |
16508 KB |
Output is correct |
59 |
Correct |
73 ms |
16500 KB |
Output is correct |
60 |
Correct |
63 ms |
16424 KB |
Output is correct |