Submission #213392

#	Time	Username	Problem	Language	Result	Execution time	Memory
213392		thebes	Stray Cat (JOI20_stray)	C++14	100 / 100	98 ms	16972 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
#define pb push_back

const int MN = 2e4+5;
int n, i, dep[MN], par[MN], col[MN], vs[MN], hm[MN];
vi ans; vector<pii> adj[MN];
queue<int> q;

vi Mark(int N,int M,int A,int B,vi U,vi V){
    ans.resize(M);
    for(i=0;i<M;i++){
        adj[U[i]].pb({V[i],i});
        adj[V[i]].pb({U[i],i});
    }
    if(A>=3){
        vs[0] = 1; q.push(0);
        while(q.size()){
            int x = q.front(); q.pop();
            for(auto v : adj[x]){
                if(!vs[v.first]){
                    vs[v.first] = 1;
                    dep[v.first] = dep[x]+1;
                    ans[v.second] = dep[x]%3;
                    q.push(v.first);
                }
                else ans[v.second]=min(dep[x],dep[v.first])%3;
            }
        }
        return ans;
    }
    else{
        int msk[]={0,0,1,0,1,1};
        q.push(0);
        while(q.size()){
            int x = q.front(); q.pop();
            if(x&&adj[x].size()==2){
                hm[x] = 1;
                if(hm[par[x]]) dep[x]=(dep[par[x]]+1)%6;
                else if(col[x]==0) dep[x]=0;
                else dep[x]=2;
                for(auto v : adj[x]){
                    if(v.first==par[x]) continue;
                    ans[v.second]=col[v.first]=msk[(dep[x]+1)%6];
                    par[v.first]=x;
                    q.push(v.first);
                }
            }
            else{
                for(auto v : adj[x]){
                    if(v.first==par[x]) continue;
                    ans[v.second]=col[v.first]=!col[x];
                    par[v.first]=x;
                    q.push(v.first);
                }
            }
        }
        return ans;
    }
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
#define pb push_back

int lst=-1, sub, ok, pat[]={0,0,1,0,1,1};
vi guess;

void Init(int A,int B){
    if(A>=3) sub=1;
    else sub=2;
}

bool match(){
    for(int i=0;i<6;i++){
        int tmp = 0;
        for(int j=0;j<guess.size();j++){
            if(guess[j]!=pat[(i+j)%6]){tmp=1;break;}
        }
        if(!tmp) return 1;
    }
    return 0;
}

int Move(vi cnt){
    if(sub==1){
        for(int i=0;i<3;i++){
            if(cnt[i]&&!cnt[(i+2)%3]) return i;
        }
    }
    else{
        int c=0;
        if(lst!=-1) cnt[lst]++;
        for(auto v : cnt) c += v;
        if(c!=2) ok=1;
        if(ok){
            if(c==2){
                cnt[lst]--;
                if(cnt[0]){lst=0;return lst;}
                else{lst=1;return lst;}
            }
            if(lst==-1){
                if(cnt[0]==1){lst=0; return 0;}
                else{lst=1; return 1;}
            }
            if(cnt[0]==1&&cnt[1]==1){lst=!lst;return lst;}
            if(cnt[lst]==1) return -1;
            else{lst=!lst; return lst;}
        }
        else{
            if(lst==-1){
                if(cnt[0]){
                    guess.pb(0);
                    if(cnt[1]){guess.pb(1); lst=1;}
                    else{guess.pb(0); lst=0;}
                }
                else{
                    guess.pb(1); guess.pb(1);
                    lst = 1;
                }
                return lst;
            }
            else{
                cnt[lst]--;
                int ot=0;
                if(cnt[1]) ot=1;
                guess.pb(ot);
                bool d1 = match();
                reverse(guess.begin(),guess.end());
                bool d2 = match();
                reverse(guess.begin(),guess.end());
                if(d1!=d2){
                    ok = 1;
                    if(d1) return -1;
                    else{lst = ot; return ot;}
                }
                lst = ot;
                return ot;
            }
        }
    }
}

Compilation message (stderr)

Catherine.cpp: In function 'bool match()':
Catherine.cpp:20:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<guess.size();j++){
                     ~^~~~~~~~~~~~~
Catherine.cpp: In function 'int Move(vi)':
Catherine.cpp:85:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• 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