| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 212956 |
2020-03-24T15:33:36 Z |
ryansee |
Stray Cat (JOI20_stray) |
C++14 |
|
335 ms |
16692 KB |
#include "Anthony.h"
#include "bits/stdc++.h"
using namespace std;
namespace {
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
// inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
// string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
typedef long long ll;
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;
#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (20006)
vector<int> v[MAXN];
// RRBRBB
int colour[] = {0,0,1,0,1,1};
} // namespace
vector<int> Mark(int n, int m, int A, int B,vector<int> U, vector<int> vv) {
FOR(i,0,m-1){
v[U[i]].eb(vv[i]), v[vv[i]].eb(U[i]);
}
vector<int> C(m);
vector<bool> V(n);
vector<int> depth(n,0);
function<void(ll,ll,ll)>dfs=[&](ll x,ll p,ll c){
V[x]=colour[c];
if(siz(v[x])-(p!=x) == 1){ // line
if(v[x][0]==p) v[x].erase(v[x].begin());
depth[v[x][0]]=depth[x]+1, dfs(v[x][0], x, (c+1)%6);
}else{
for(auto i:v[x])if(i^p){
depth[i]=depth[x]+1, dfs(i,x,(V[x]==1?0:1));
}
}
};
dfs(0,0,0);
FOR(i,0,m-1){ll a=U[i],b=vv[i];
if(depth[a]<depth[b])swap(a,b);
C[i]=V[a];
cerr<<a<<' '<<b<<' '<<C[i]<<'\n';
}
return C;
}
#include "Catherine.h"
#include "bits/stdc++.h"
using namespace std;
namespace {
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
// inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
// string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
typedef long long ll;
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;
#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (20006)
ll A, B, start, lst=-1, gg=0, bckt=0;
vector<int> C;
map<vector<int>,bool> mp;
int colour[] = {0,0,1,0,1,1};
} // namespace
void Init(int A, int B) {
::C.clear(), ::mp.clear();
::start=1, ::A=A, ::B=B;
FOR(i,0,5) {
vector<int> tmp;
DEC(j,i,i-4) tmp.pb(colour[(j+6)%6]);
mp[tmp]=1;
}
}
int Move(vector<int> y) {
int deg=accumulate(all(y), 0ll);
if(start){
start=0;
assert(deg>0);
if(deg==1){
lst=y[0]?0:1;
return lst;
}else if(deg==2){
gg=1;
FOR(i,0,1) FOR(j,1,y[i]) C.pb(i);
return lst=(y[1]?1:0);
}else{ // >2
assert(y[0]==1||y[1]==1);
return lst = (y[0]==1 ? 0 : 1);
}
}
if(bckt) {
if(siz(C)==1){
gg=0, bckt=0, assert(deg==1);
C.clear();
return lst = (y[0]?0:1);
}else{
cbr;
C.pop_back();
assert((y[0]==1)+(y[1]==1)==1);
return lst=(y[0]?0:1);
}
}
if(gg) {// rmbr +1 to deg
if(deg==0){
cerr<<"no\n";
C.pop_back();bckt=1;
return lst=-1;
}else if(deg==1){
if(y[0]) C.pb(0); else C.pb(1);
if(siz(C)<5){
return lst=(y[0]?0:1);
}else{assert(siz(C)==5); // pop 2
for(auto i:C) cerr<<i<<' '; cerr<<'\n';
if(mp[C]){// correct
gg=0;
C.clear();
return lst=(y[0]?0:1);
}else{
bckt=1;
C.pop_back(), C.pop_back();
cerr<<"flip\n";
return lst=-1;
}
}
}else { // deg + 1 > 2
if(y[0]==0||y[1]==0){// wrong
bckt=1;
C.pop_back();
cerr<<y[0]<<' '<<y[1]<<'\n';
return lst=-1;
}else{
gg=0;
C.clear();
}
}
}
assert(lst!=-1);
ll zero=y[0],one=y[1];
lst ? ++ one : ++ zero;
if(one==1&&zero==1){
lst ^= 1; return lst;
}
if(min(one,zero)==0){
return lst;
}
if(zero == 1 || one == 1); else assert(0);
if(zero==1) { return lst=0; }
else { return lst=1; }
}
/*
7 6 2 6 4
0 2
0 4
1 2
1 3
1 5
4 6
*/
Compilation message
Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:88:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(auto i:C) cerr<<i<<' '; cerr<<'\n';
^~~
Catherine.cpp:88:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(auto i:C) cerr<<i<<' '; cerr<<'\n';
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
314 ms |
16692 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
314 ms |
16692 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
14500 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
14500 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
1792 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
299 ms |
11416 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
335 ms |
11432 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
