Submission #912308

#	Time	Username	Problem	Language	Result	Execution time	Memory
912308		winter0101	Stray Cat (JOI20_stray)	C++14	100 / 100	47 ms	17008 KiB

Anthony

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=2e4+9;
//pattern la 010011 thi voi moi cyclic thi dao nguoc deu khong co
vector<int>a[maxn];
vector<pii>g[maxn];
bool vis[maxn];
int d[maxn];
int b[12]={0,1,0,0,1,1,0,1,0,0,1,1};
vector<int>id;
int msk[maxn];
int xr=0;
void dfs(int u,int par){
int cnt=0;
for (auto v:g[u]){
if (v.fi==par)continue;
cnt++;
}
if (cnt>1||cnt==0){
int nw=0;
for1(i,0,11){
if (xr==b[i]){
nw=i;
break;
}
}
int lst=0;
for1(i,0,sz(id)-1){
msk[id[i]]=b[nw];
lst=msk[id[i]];
nw=(nw+1)%12;
}
id.clear();
xr=(lst^1);
}
int xd=xr;
for (auto v:g[u]){
if (v.fi==par)continue;
id.pb(v.se);
dfs(v.fi,u);
xr=xd;
}
}
std::vector<int> Mark(int N, int M, int A, int B,std::vector<int> U, std::vector<int> V) {
  int n=N,m=M;
  if (B==0){
  std::vector<int> x(M);
  for1(i,0,m-1){
  a[U[i]].pb(V[i]);
  a[V[i]].pb(U[i]);
  }
  vis[0]=1;
  queue<int>t;
  t.push(0);
  while (!t.empty()){
  auto u=t.front();
  t.pop();
  for (auto v:a[u]){
  if (vis[v])continue;
  d[v]=d[u]+1;
  t.push(v);
  vis[v]=1;
  }
  }
  for (int i = 0; i < M; ++i) {
  int u=U[i],v=V[i];
  if (d[u]==d[v]){
  int t1=(d[u]%3),t2=(t1+1)%3;
  if (t1==1||t2==1)x[i]|=(1<<0);
  if (t1==2||t2==2)x[i]|=(1<<1);
  x[i]--;
  continue;
  }
  if (d[u]>d[v])swap(u,v);
  int mask=0;
  if (d[u]%3==2||d[v]%3==2)mask|=(1<<1);
  if (d[u]%3==1||d[v]%3==1)mask|=(1<<0);
  x[i]=mask-1;
  }
  return x;
  }
  else {
  for1(i,0,m-1){
  g[U[i]].pb({V[i],i});
  g[V[i]].pb({U[i],i});
  }
  dfs(0,0);
  vector<int>x(M);
  for1(i,0,m-1)x[i]=msk[i];
  //for1(i,0,m-1)cout<<U[i]<<" "<<V[i]<<" "<<x[i]<<'\n';
  return x;
  }
}

Catherine

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
namespace {
 
int A, B;
int step = 0;
int nw=0;
}  // namespace
int c[12]={0,1,0,0,1,1,0,1,0,0,1,1};
set<int>patt;
void Init(int A, int B) {
  ::A = A;
  ::B = B;
  if (B==0){
  return;
  }
  for1(i,0,11-5+1){
  int cc=0,sum=0;
  for1(j,i,i+4){
  sum+=c[j]*(1<<cc);
  cc++;
  }
  patt.insert(sum);
  }
}
int cnt[3];
bool detact=false;
int lst=-1;
vector<int>xx,yy;
int Move(std::vector<int> y) {
  //
  if (B==0){
  int ct=0;
  for1(i,0,2){
  if (y[i]!=0)ct++;
  }
  if (ct==1){
  for1(i,0,2){
  if (y[i]!=0)return i;
  }
  }
  for1(i,0,2)cnt[i]=0;
  for1(i,0,2){
  if (y[i]!=0){
  int j=i+1;
  for1(k,0,1){
  if (j>>k&1){
  cnt[(1<<k)]++;
  }
  else {
  cnt[0]++;
  }
  }
  }
  }
  for1(i,0,2){
  if (cnt[i]==2){
  int ans=i;
  int gg=(i-1+3)%3;
  ans+=gg;
  return ans-1;
  }
  }
  }
  //
  nw++;
  /*cout<<"STEP "<<nw<<'\n';
  for1(i,0,A-1)cout<<y[i]<<" ";
  cout<<'\n';*/
  int deg=(nw>1);
  for1(i,0,A-1)deg+=y[i];
  if (nw==1&&deg>=3){
  for1(i,0,A-1){
  if (y[i]==1){
  lst=i;
  detact=1;
  return i;
  }
  }
  }
  if (nw==1&&deg==1){
  step=0;
  detact=1;
  xx.clear();
  for1(i,0,A-1){
  if (y[i]==1){
  lst=i;
  return i;
  }
  }
  }
  //cerr<<deg<<" "<<detact<<'\n';
  if (deg>=3&&!detact){
  if (lst!=-1)y[lst]++;
  detact=1;
  for1(i,0,A-1){
  if (y[i]==1){
  if (i==lst){
  lst=xx.back();
  xx.pop_back();
  step=0;
  return -1;
  }
  xx.clear();
  step=0;
  lst=i;
  return i;
  }
  }
  }
  int gg=0;
  for1(i,0,A-1){
  gg+=y[i];
  }
  if (gg==0){
  detact=1;
  }
  //cerr<<"STEP "<<nw<<" "<<detact<<" "<<sz(xx)<<'\n';
  if (!detact){
  step++;
  for1(i,0,A-1){
  for1(j,1,y[i]){
  yy.pb(i);
  }
  }
  if (nw<4){
  lst=yy.back();
  xx.pb(lst);
  return yy.back();
  }
  if (step==4){
  int mk=0;
  for1(i,0,4){
  mk+=yy[i]*(1<<i);
  }
  if (patt.find(mk)==patt.end()){
  step=0;
  detact=1;
  xx.clear();
  }
  else {
  detact=1;
  }
  }
  }
  //cerr<<"STEP "<<detact<<" "<<sz(xx)<<'\n';
  //cerr<<"check "<<detact<<'\n';
  if (detact) {
  if (step){
  lst=xx.back();
  xx.pop_back();
  step=0;
  return -1;
  }
  else {
  if (!xx.empty()){
  lst=xx.back();
  xx.pop_back();
  return lst;
  }
  if (gg==1){
  for1(i,0,A-1){
  if (y[i]==1){
  lst=i;
  return i;
  }
  }
  }
  if (lst!=-1)y[lst]++;
  for1(i,0,A-1){
  if (y[i]==1){
  lst=i;
  return i;
  }
  }
  }
  }
}

Compilation message (stderr)

Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:59:7: warning: unused variable 'n' [-Wunused-variable]
   59 |   int n=N,m=M;
      |       ^

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:192:1: warning: control reaches end of non-void function [-Wreturn-type]
  192 | }
      | ^

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 71 / 71
• Subtask 7: 9 / 9