Submission #951169

#	Time	Username	Problem	Language	Result	Execution time	Memory
951169		hotboy2703	Stray Cat (JOI20_stray)	C++14	100 / 100	40 ms	20060 KiB

Anthony

#include<bits/stdc++.h>
#include "Anthony.h"
using namespace std;
//using ll = long long;
using ll = int;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
namespace {
    string magic = "110010110010";
    ll good[2][12];
    vector <ll> u1,v1;

    ll Cat;
    vector <ll> last_move;
    vector <ll> all_y;
    bool chay_ngay_di;

    void init(){
        memset(good,-1,sizeof good);
        for (ll i = 0;i < sz(magic);i ++){
            for (ll j = 0;j < sz(magic);j ++){
                if (magic[(j+i)%sz(magic)]==magic[j])good[magic[j]-'0'][i] = j;
            }
        }
    }
    vector <ll> g[20010];
    ll dist[20010];
    void bfs(){
        memset(dist,-1,sizeof dist);
        dist[0] = 0;
        queue <ll> q;
        q.push(0);
        while (!q.empty()){
            ll u = q.front();
            q.pop();
            for (auto v:g[u]){
                if (dist[v]==-1){
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
    }
    vector <ll> path;
    vector <ll> ans;
    void dfs(ll u,ll p){
        if (sz(g[u])==2 && u != 0){
            for (auto edge:g[u]){
                ll v = u1[edge];
                if (v==u)v=v1[edge];

                if (v==p)continue;
                path.push_back(edge);
                dfs(v,u);
            }
        }
        else{
            ll color = 0;
            if (sz(path)>=2){
                ll ptr = good[ans[path[0]]][(sz(path)-1)%12];
                for (ll j = sz(path)-1;j>=0;j--,ptr=(ptr+1)%12){
                    ans[path[j]] = magic[ptr]-'0';
                }
                color = ans[path[0]];
            }
            else if (sz(path)==1){
                color = ans[path[0]];
            }
            else{
                color = 0;
            }
            path.clear();
            for (auto edge:g[u]){
                ll v = u1[edge];
                if (v==u)v=v1[edge];

                if (v==p){continue;}

                ans[edge] = 1-color;
                path.push_back(edge);
                dfs(v,u);
            }
        }
    }
}
std::vector<ll> Mark(ll n, ll m, ll a, ll b,std::vector<ll> u, std::vector<ll> v){
    init();
    if (a >= 3){
        for (ll i = 0;i < m;i ++)g[u[i]].push_back(v[i]),g[v[i]].push_back(u[i]);
        bfs();
        vector <ll> res(m);
        vector <set <ll> >  color(n);
        for (ll i = 0;i < m;i ++){
            if (dist[u[i]] == dist[v[i]]){
                res[i] = (dist[u[i]]%3)%3;
            }
            else{
                if (dist[u[i]] + 1 == dist[v[i]])swap(u[i],v[i]);
                res[i] = dist[v[i]]%3;
            }
            color[u[i]].insert(res[i]);
            color[v[i]].insert(res[i]);
        }
        return res;
    }
    else{
        u1 = u,v1 = v;
        for (ll i = 0;i < m;i ++){
            g[u[i]].push_back(i);
            g[v[i]].push_back(i);
        }
        ans.resize(m);
        dfs(0,0);

        return ans;
    }
}
void Init(ll a,ll b){
    Cat = a;
    init();
}
ll sadasd = 0;
ll Move(vector <ll> y){
    if (Cat>=3){
        if (sz(last_move))y[last_move.back()]++;
        ll cnt = 0;
        for (auto x:y)cnt+=x>0;
        if (cnt==1){
            ll ptr=0;
            for (auto x:y){
                if (x>0){
                    last_move.push_back(ptr);
                    return ptr;
                }
                ptr++;
            }
        }
        for (ll j = 0;j < 3;j ++){
            if (!y[j]){
                last_move.push_back((j+1)%3);
                return (j+1)%3;
            }
        }
    }
    vector <ll> sus = y;
    vector <ll> tmp;
    for (ll j = 0;j < sz(y);j ++){
        while (y[j]--)tmp.push_back(j);
    }
    y = tmp;
    all_y.insert(all_y.end(),y.begin(),y.end());
    auto small = [&](){
        ll cnt[2] = {};
        if (sz(last_move)){
            ll x = last_move.back();
            if (x==-1)x=last_move[sz(last_move)-2];
            cnt[x]++;
        }
        for (auto x:y){
            cnt[x]++;
        }
        if (cnt[0]==1)return 0;
        else return 1;
    };
    auto upd = [&](ll x){
        if (x!=-1&&sus[x]==0)x=-1;
        last_move.push_back(x==-1?last_move.back() : x);
        return x;
    };
    if (chay_ngay_di){
        if (sz(y)==1){
            return upd(y.back());
        }
        else{
            return upd(small());
        }
    }
    else{
        if (sz(last_move)==0){
            if (sz(y)!=2){
                chay_ngay_di = 1;
                return upd(small());
            }
            else{
                return upd(y.back());
            }
        }
        else{
            if (sz(y) == 0){
                chay_ngay_di = 1;
                return upd(-1);
            }
            else if (sz(y) >= 2){
                chay_ngay_di = 1;
                return upd(small());
            }
            else{
                if (sz(last_move)==3){
                    chay_ngay_di = 1;
                    string sus;
                    for (auto x:all_y)sus.push_back(x+'0');
                    string double_magic = magic+magic;
                    bool ok = 0;
                    for (ll j = 0;j + 4 < sz(double_magic);j ++){
                        if (sus == double_magic.substr(j,5)){
                            ok = 1;
                            break;
                        }
                    }
                    if (ok){
                        return upd(y[0]);
                    }
                    else{
                        return upd(-1);
                    }
                }
                else{
                    return upd(y.back());
                }
            }
        }
    }
}

Catherine

#include<bits/stdc++.h>
#include "Catherine.h"
using namespace std;
//using ll = long long;
using ll = int;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
namespace {
    string magic = "110010110010";
    ll good[2][12];
    vector <ll> u1,v1;

    ll Cat;
    vector <ll> last_move;
    vector <ll> all_y;
    bool chay_ngay_di;

    void init(){
        memset(good,-1,sizeof good);
        for (ll i = 0;i < sz(magic);i ++){
            for (ll j = 0;j < sz(magic);j ++){
                if (magic[(j+i)%sz(magic)]==magic[j])good[magic[j]-'0'][i] = j;
            }
        }
    }
    vector <ll> g[20010];
    ll dist[20010];
    void bfs(){
        memset(dist,-1,sizeof dist);
        dist[0] = 0;
        queue <ll> q;
        q.push(0);
        while (!q.empty()){
            ll u = q.front();
            q.pop();
            for (auto v:g[u]){
                if (dist[v]==-1){
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
    }
    vector <ll> path;
    vector <ll> ans;
    void dfs(ll u,ll p){
        if (sz(g[u])==2 && u != 0){
            for (auto edge:g[u]){
                ll v = u1[edge];
                if (v==u)v=v1[edge];

                if (v==p)continue;
                path.push_back(edge);
                dfs(v,u);
            }
        }
        else{
            ll color = 0;
            if (sz(path)>=2){
                ll ptr = good[ans[path[0]]][(sz(path)-1)%12];
                for (ll j = sz(path)-1;j>=0;j--,ptr=(ptr+1)%12){
                    ans[path[j]] = magic[ptr]-'0';
                }
                color = ans[path[0]];
            }
            else if (sz(path)==1){
                color = ans[path[0]];
            }
            else{
                color = 0;
            }
            path.clear();
            for (auto edge:g[u]){
                ll v = u1[edge];
                if (v==u)v=v1[edge];

                if (v==p){continue;}

                ans[edge] = 1-color;
                path.push_back(edge);
                dfs(v,u);
            }
        }
    }
}
std::vector<ll> Mark(ll n, ll m, ll a, ll b,std::vector<ll> u, std::vector<ll> v){
    init();
    if (a >= 3){
        for (ll i = 0;i < m;i ++)g[u[i]].push_back(v[i]),g[v[i]].push_back(u[i]);
        bfs();
        vector <ll> res(m);
        vector <set <ll> >  color(n);
        for (ll i = 0;i < m;i ++){
            if (dist[u[i]] == dist[v[i]]){
                res[i] = (dist[u[i]]%3)%3;
            }
            else{
                if (dist[u[i]] + 1 == dist[v[i]])swap(u[i],v[i]);
                res[i] = dist[v[i]]%3;
            }
            color[u[i]].insert(res[i]);
            color[v[i]].insert(res[i]);
        }
        return res;
    }
    else{
        u1 = u,v1 = v;
        for (ll i = 0;i < m;i ++){
            g[u[i]].push_back(i);
            g[v[i]].push_back(i);
        }
        ans.resize(m);
        dfs(0,0);

        return ans;
    }
}
void Init(ll a,ll b){
    Cat = a;
    init();
}
ll sadasd = 0;
ll Move(vector <ll> y){
    if (Cat>=3){
        if (sz(last_move))y[last_move.back()]++;
        ll cnt = 0;
        for (auto x:y)cnt+=x>0;
        if (cnt==1){
            ll ptr=0;
            for (auto x:y){
                if (x>0){
                    last_move.push_back(ptr);
                    return ptr;
                }
                ptr++;
            }
        }
        for (ll j = 0;j < 3;j ++){
            if (!y[j]){
                last_move.push_back((j+1)%3);
                return (j+1)%3;
            }
        }
    }
    vector <ll> sus = y;
    vector <ll> tmp;
    for (ll j = 0;j < sz(y);j ++){
        while (y[j]--)tmp.push_back(j);
    }
    y = tmp;
    all_y.insert(all_y.end(),y.begin(),y.end());
    auto small = [&](){
        ll cnt[2] = {};
        if (sz(last_move)){
            ll x = last_move.back();
            if (x==-1)x=last_move[sz(last_move)-2];
            cnt[x]++;
        }
        for (auto x:y){
            cnt[x]++;
        }
        if (cnt[0]==1)return 0;
        else return 1;
    };
    auto upd = [&](ll x){
        if (x!=-1&&sus[x]==0)x=-1;
        last_move.push_back(x==-1?last_move.back() : x);
        return x;
    };
    if (chay_ngay_di){
        if (sz(y)==1){
            return upd(y.back());
        }
        else{
            return upd(small());
        }
    }
    else{
        if (sz(last_move)==0){
            if (sz(y)!=2){
                chay_ngay_di = 1;
                return upd(small());
            }
            else{
                return upd(y.back());
            }
        }
        else{
            if (sz(y) == 0){
                chay_ngay_di = 1;
                return upd(-1);
            }
            else if (sz(y) >= 2){
                chay_ngay_di = 1;
                return upd(small());
            }
            else{
                if (sz(last_move)==3){
                    chay_ngay_di = 1;
                    string sus;
                    for (auto x:all_y)sus.push_back(x+'0');
                    string double_magic = magic+magic;
                    bool ok = 0;
                    for (ll j = 0;j + 4 < sz(double_magic);j ++){
                        if (sus == double_magic.substr(j,5)){
                            ok = 1;
                            break;
                        }
                    }
                    if (ok){
                        return upd(y[0]);
                    }
                    else{
                        return upd(-1);
                    }
                }
                else{
                    return upd(y.back());
                }
            }
        }
    }
}

• 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