| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 951167 | hotboy2703 | Stray Cat (JOI20_stray) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "stray.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());
}
}
}
}
}
#include<bits/stdc++.h>
#include "stray.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());
}
}
}
}
}