Submission #764495

#	Time	Username	Problem	Language	Result	Execution time	Memory
764495		ngrace	Stray Cat (JOI20_stray)	C++14	100 / 100	39 ms	16108 KiB

Anthony

#include <bits/stdc++.h>
#include "Anthony.h"
using namespace std;
#define v vector
#define ii pair<int,int>
#define fi first
#define se second

namespace {

int FunctionExample(int i, int A) {
  return i % A;
}

}  // namespace

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] = -1;//FunctionExample(i, A);
  }

  v<int> seq = {1,0,1,1,0,0};

  v<v<ii>> adj(N);
  for(int i=0; i<M; i++){
    adj[U[i]].push_back({V[i],i});
    adj[V[i]].push_back({U[i],i});
  }

  queue<ii> q;
  v<bool> vis(N,false);
  q.push({0,0});
  while(q.size()>0){
    int cur=q.front().fi;
    int dep=q.front().se;
    q.pop();

    if(vis[cur]) continue;
    vis[cur]=true;

    int last=-1;
    int lastind=-1;
    for(ii it:adj[cur]){
      if(X[it.se]!=-1){
        last=X[it.se];
        lastind=it.se;
      }
    }

    if(A>2){
      for(ii it:adj[cur]){
        if(!vis[it.fi]) X[it.se] = dep%3;
      }
    }
    else if(cur==0){
      for(ii it:adj[cur]) X[it.se] = seq[0];
    }else{
      if(adj[cur].size()>2){
        for(ii it:adj[cur]){
          if(it.se!=lastind) X[it.se] = (last+1)%2;
          if(last==1) dep=1;
          else dep=0;
        }
      } else{
        for(ii it:adj[cur]){
          if(it.se!=lastind) X[it.se] = seq[dep%6];
        }
      }
    }

    for(ii it:adj[cur]){
      if(!vis[it.fi]) q.push({it.fi, dep+1});
    }
  }

  //for(int i:X) cout<<i<<" ";
  //cout<<endl;

  return X;
}

Catherine

#include <bits/stdc++.h>
#include "Catherine.h"
using namespace std;
#define v vector
#define ii pair<int,int>
#define fi first
#define se second

namespace {

int A, B;
int lastmark = -1;
v<int> seq = {0,0,1,1,0,1};
v<int> moves;
bool allgood = false;

}  // namespace

void Init(int A, int B) {
  ::A = A;
  ::B = B;
}

int Move(std::vector<int> y) {
  if(A>2){
    if(lastmark==-1){
      if(y[0]==y[1] && y[0]==0) return lastmark=2;
      else if(y[1]==y[2] && y[1]==0) return lastmark=0;
      else if(y[2]==y[0] && y[0]==0) return lastmark=1;
    } else y[lastmark]++;
    //cout<<lastmark<<" "<<y[0]<<" "<<y[1]<<" "<<y[2]<<endl;
    if(y[0]>0 && y[1]>0) return lastmark = 0;
    else if(y[1]>0&&y[2]>0) return lastmark=1;
    else return lastmark=2;
  }

  int numedge=y[0]+y[1] + (lastmark!=-1);
  
  //cout<<y[0]<<" "<<y[1]<<" "<<lastmark<<endl;

  if(lastmark==-1){
    if(numedge>2){
      allgood=true;
      lastmark = (y[0]>y[1]) ? 1 : 0;
      return lastmark;
    } else if(numedge==1){
      allgood=true;
      lastmark = (y[0]>0) ? 0 : 1;
      return lastmark;
    } 
    else{
      lastmark = (y[0]>0) ? 0 : 1;
      //cout<<"?"<<y[0]<<" "<<y[1]<<" "<<lastmark<<endl;
      moves.push_back((y[lastmark]>1) ? lastmark : (lastmark+1)%2);
      moves.push_back(lastmark);
      return lastmark;
    }
  } 

  
  if(numedge>2){
    int old=lastmark;
    y[lastmark]++;
    lastmark = (y[0]>y[1]) ? 1 : 0;
    allgood=true;
    return (old==lastmark) ? -1 : lastmark;
  }

  if(numedge==1){
    allgood=true;
    return -1;
  }

  if(allgood){
    lastmark = (y[0]==1) ? 0 : 1;
    return lastmark;
  }

  if(moves.size()==4){
    //cout<<"!"<<moves[0]<<" "<<moves[1]<<" "<<moves[2]<<" "<<moves[3]<<endl;
    bool found=false;
    int next=-1;
    for(int i=0; i<6; i++){
      if(moves[0]==seq[i] && moves[1]==seq[(i+1)%6] && moves[2]==seq[(i+2)%6] && moves[3]==seq[(i+3)%6]){
        found=true;
        next=seq[(i+4)%6];
      }
    }
    if(!found || y[next]==0){
      allgood=true;
      return -1;
    }
  }

  lastmark = (y[0]==1) ? 0 : 1;
  moves.push_back(lastmark);
  return lastmark;
}

Compilation message (stderr)

Anthony.cpp:11:5: warning: 'int {anonymous}::FunctionExample(int, int)' defined but not used [-Wunused-function]
   11 | int FunctionExample(int i, int A) {
      |     ^~~~~~~~~~~~~~~

• 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