Submission #1317337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317337		user736482	Spy 3 (JOI24_spy3)	C++20	0 / 100	14 ms	3700 KiB

Aoi

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define INF 1000000001LL
#define POT (1LL<<20)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define FCTCST 7
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U,typename Z>
pair<T, U> operator*(const pair<T, U>& a, const Z& b) {
    return {a.first*b, a.second*b};
}
template<typename T, typename U,typename Z>
pair<T, U> operator/(const pair<T, U>& a, const Z& b) {
    return {a.first/b, a.second/b};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os<<"{"<<p.ff<<", "<<p.ss<<"}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}
template<ll MOD=998244353>
struct mint_t{
    ll x;
    mint_t(ll y=0){x=y%MOD;if(x<0)x+=MOD;}
    mint_t& operator+=(const mint_t& a){if((x+=a.x)>=MOD)x-=MOD;return *this;}
    mint_t& operator-=(const mint_t& a){if((x+=MOD-a.x)>=MOD)x-=MOD;return *this;}
    mint_t operator+(const mint_t& a)const{mint_t res(*this);return res+=a;}
    mint_t operator-(const mint_t& a)const{mint_t res(*this);return res-=a;}
    mint_t& operator*=(const mint_t& a){(x*=a.x)%=MOD;return *this;}
    mint_t operator*(const mint_t& a)const{mint_t res(*this);return res*=a;}
    mint_t fp(ll y)const{
        mint_t a=1,b=x;
        while(y){
            if(y&1)a*=b;
            b*=b;
            y/=2;
        }
        return a;
    }
    mint_t& operator/=(const mint_t& a){(*this)*=a.fp(MOD-2);return *this;}
    mint_t operator/(const mint_t& a)const{mint_t res(*this);return res/=a;}
};
#define mint mint_t<>
template<long long MOD>
istream& operator>>(istream& in, mint_t<MOD>& a){
    ll x;
    in>>x;
    a=mint_t<MOD>(x);
    return in;
}
template<long long MOD>
istream& operator<<(istream& out, mint_t<MOD>& a){
    out<<a.x;
    return out;
}
mint fct[FCTCST];
mint bnm(ll a,ll b){
    if(b>a || a<0)return 0;
    return fct[a]/fct[b]/fct[a-b];
}
ll pop[10007],pop2[300];
vi g[10007];
ll mj[16];
ll zl[20007];
bool vs2[10007];
string ms[300];
string to_bin(ll x,ll bt){
    string rs;
    while(bt--){rs.pb('0'+x%2);x/=2;}
    rev(rs);return rs;
}
ll to_int(string s){
    ll rs=0;
    for(char c:s){
        rs*=2;rs+=c-'0';
    }
    return rs;
}
std::string aoi(int n, int m, int q, int k, std::vector<int> a,
std::vector<int> b, std::vector<long long> c,
std::vector<int> t, std::vector<int> x){
    for(ll i=0;i<k;i++)zl[x[i]]=i+1;
    for(ll i=0;i<m;i++){
        g[a[i]].pb(i);g[b[i]].pb(i);
    }assert(n<10007);
    for(ll i=0;i<n;i++)pop[i]=-2;while(n)n++;
    priority_queue<pip,vector<pip>,greater<pip>>pq;
    pq.push({0,{0,-1}});while(n)n++;
    while(pq.size()){
        pip x=pq.top();
        pq.pop();
        if(pop[x.ss.ff]!=-2)continue;
        pop[x.ss.ff]=x.ss.ss;
        for(ll i :g[x.ss.ff]){
            pq.push({x.ff+c[i],{a[i]^b[i]^x.ss.ff,i}});
        }
    }
    //for(ll i=0;i<n;i++)cout<<pop[i]<<" ";cout<<flush;
    //cout<<"\n";
    vvi v;while(n)n++;
    for(ll i=0;i<q;i++){
      mj[i]=300;
      ll x=t[i];
      vi pm;
      while(pop[x]!=-1){
        if(zl[pop[x]]){pm.pb(zl[pop[x]]-1);
          if(vs2[pop[x]]){pm.pop_back();
            mj[i]=pop[x];break;
          }
          vs2[pop[x]]=1;
        }
        x^=a[pop[x]]^b[pop[x]];
        
      }
      v.pb(pm);
    }
    v.pb({});
    for(ll i=0;i<k;i++)if(!vs2[i])v.back().pb(i);
    //for(ll i=0;i<q;i++)cout<<mj[i]<<" ";
    //cout<<v<<flush;
    while(n)n++;
    vii v2;
    for(ll i=0;i<v.size();i++){
      v2.pb({v[i].size(),i});
    }
    sort(al(v2));
    ll mr1=v2[0].ss,mr2=v2[1].ss;
    if(mr1>mr2)swap(mr1,mr2);
    //cout<<mr1<<" "<<mr2<<"\n";
    string rs="";
    for(vi i:v)rs.pb('0');
    rs[mr1]=rs[mr2]='1';
    for(ll i=0;i<v.size();i++){
      ll x=i;
      if(x==mr2)x=mr1;
      if(x>mr2)x--;
      string pm=to_bin(x,4);
      if(x==mr1){
        pm.pb('0'+(i!=x));
      }
      for(ll j:v[i])ms[j]=pm;
    }
    for(ll i=0;i<k;i++)rs+=ms[i]+to_bin(mj[i],9);
    //cout<<rs<<endl;
    
    return rs;
}

void answer(const std::vector<int> &e);
string gt(string& st,ll x){
  string rs;
  //if(st.size()<x)cout<<"xd"<<flush;
  for(ll i=0;i<x;i++)rs.pb(st[i]);
  for(ll i=0;i<x;i++)st.erase(st.begin());
  return rs;
}
void bitaro(int n, int m, int q, int k, std::vector<int> a, std::vector<int> b,
std::vector<long long> c, std::vector<int> t, std::vector<int> x,
std::string s){
  for(ll i=0;i<k;i++)zl[x[i]]=i+1;
  vvi v(q+1);
  ll mr1=-1,mr2;
  for(ll i=0;i<=q;i++){
    ll x=to_int(gt(s,1));
    if(x)if(mr1==-1)mr1=i;else mr2=i;
  }
  //cout<<mr1<<" "<<mr2<<"\n"<<flush;
  for(ll i=0;i<k;i++){
    ll x=to_int(gt(s,4));//cout<<x<<" "<<flush;
    if(x>=mr2)x++;
    if(x==mr1)if(to_int(gt(s,1)))x=mr2;
    v[x].pb(i);
    mj[i]=to_int(gt(s,9));
    //cout<<"xd"<<flush;
  }
  //for(ll i=0;i<k;i++)cout<<mj[i]<<" ";cout<<"\n";
  //cout<<v<<"\n";
  for(ll i=0;i<k;i++)pop2[i]=300;
  for(ll i=0;i<q;i++){
    for(ll i=0;i<n;i++)pop[i]=-2;
    for(ll j=0;j<n;j++)g[j].clear();
    while(mj[i]!=300){
      //cout<<mj[i]<<" "<<pop[mj[i]]<<" "<<x[mj[i]];return;
      v[i].pb(x[mj[i]]);
      mj[i]=pop2[mj[i]];
    }
    for(ll j:x)c[j]=1000000000000001LL;
    for(ll j:v[i]){
      g[a[x[j]]].pb(x[j]);
      g[b[x[j]]].pb(x[j]);
      c[x[j]]=0;
      //cout<<x[j]<<" ";
    }
    for(ll j=0;j<m;j++){
      if(!zl[j]){
        g[a[j]].pb(j);g[b[j]].pb(j);
      }
    }
    //for(ll i=0;i<n;i++){cout<<i<<": "<<g[i]<<"\n";}
    priority_queue<pip,vector<pip>,greater<pip>>pq;
    pq.push({0,{0,-1}});
    while(pq.size()){
        pip x=pq.top();
       // cout<<x<<"\n";
        pq.pop();
        if(pop[x.ss.ff]!=-2)continue;
        pop[x.ss.ff]=x.ss.ss;
        for(ll i :g[x.ss.ff]){
            pq.push({x.ff+c[i],{a[i]^b[i]^x.ss.ff,i}});
        }
    }
    vi rs;
    ll pp=-1;
    vector<int> vp;
    while(t[i]){
      vp.pb(pop[t[i]]);
      if(t[i]^a[pop[t[i]]]^b[pop[t[i]]]==0)break;
      if(zl[pop[t[i]]]){
        if(pp!=-1)
        pop2[pp]=zl[pop[t[i]]]-1;
        pp=zl[pop[t[i]]]-1;
      }
      t[i]^=a[pop[t[i]]]^b[pop[t[i]]];
    }
    rev(vp);
    //cout<<vp<<"\n";
    answer(vp);
    
  }

  //cout<<v;
}

Bitaro

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define INF 1000000001LL
#define POT (1LL<<20)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define FCTCST 7
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U,typename Z>
pair<T, U> operator*(const pair<T, U>& a, const Z& b) {
    return {a.first*b, a.second*b};
}
template<typename T, typename U,typename Z>
pair<T, U> operator/(const pair<T, U>& a, const Z& b) {
    return {a.first/b, a.second/b};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os<<"{"<<p.ff<<", "<<p.ss<<"}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}
template<ll MOD=998244353>
struct mint_t{
    ll x;
    mint_t(ll y=0){x=y%MOD;if(x<0)x+=MOD;}
    mint_t& operator+=(const mint_t& a){if((x+=a.x)>=MOD)x-=MOD;return *this;}
    mint_t& operator-=(const mint_t& a){if((x+=MOD-a.x)>=MOD)x-=MOD;return *this;}
    mint_t operator+(const mint_t& a)const{mint_t res(*this);return res+=a;}
    mint_t operator-(const mint_t& a)const{mint_t res(*this);return res-=a;}
    mint_t& operator*=(const mint_t& a){(x*=a.x)%=MOD;return *this;}
    mint_t operator*(const mint_t& a)const{mint_t res(*this);return res*=a;}
    mint_t fp(ll y)const{
        mint_t a=1,b=x;
        while(y){
            if(y&1)a*=b;
            b*=b;
            y/=2;
        }
        return a;
    }
    mint_t& operator/=(const mint_t& a){(*this)*=a.fp(MOD-2);return *this;}
    mint_t operator/(const mint_t& a)const{mint_t res(*this);return res/=a;}
};
#define mint mint_t<>
template<long long MOD>
istream& operator>>(istream& in, mint_t<MOD>& a){
    ll x;
    in>>x;
    a=mint_t<MOD>(x);
    return in;
}
template<long long MOD>
istream& operator<<(istream& out, mint_t<MOD>& a){
    out<<a.x;
    return out;
}
mint fct[FCTCST];
mint bnm(ll a,ll b){
    if(b>a || a<0)return 0;
    return fct[a]/fct[b]/fct[a-b];
}
ll pop[10007],pop2[300];
vi g[10007];
ll mj[16];
ll zl[20007];
bool vs2[10007];
string ms[300];
string to_bin(ll x,ll bt){
    string rs;
    while(bt--){rs.pb('0'+x%2);x/=2;}
    rev(rs);return rs;
}
ll to_int(string s){
    ll rs=0;
    for(char c:s){
        rs*=2;rs+=c-'0';
    }
    return rs;
}
std::string aoi(int n, int m, int q, int k, std::vector<int> a,
std::vector<int> b, std::vector<long long> c,
std::vector<int> t, std::vector<int> x){
    for(ll i=0;i<k;i++)zl[x[i]]=i+1;
    for(ll i=0;i<m;i++){
        g[a[i]].pb(i);g[b[i]].pb(i);
    }
    for(ll i=0;i<n;i++)pop[i]=-2;
    priority_queue<pip,vector<pip>,greater<pip>>pq;
    pq.push({0,{0,-1}});
    while(pq.size()){
        pip x=pq.top();
        pq.pop();
        if(pop[x.ss.ff]!=-2)continue;
        pop[x.ss.ff]=x.ss.ss;
        for(ll i :g[x.ss.ff]){
            pq.push({x.ff+c[i],{a[i]^b[i]^x.ss.ff,i}});
        }
    }
    //for(ll i=0;i<n;i++)cout<<pop[i]<<" ";cout<<flush;
    //cout<<"\n";
    vvi v;
    for(ll i=0;i<q;i++){
      mj[i]=300;
      ll x=t[i];
      vi pm;
      while(pop[x]!=-1){
        if(zl[pop[x]]){pm.pb(zl[pop[x]]-1);
          if(vs2[pop[x]]){pm.pop_back();
            mj[i]=pop[x];break;
          }
          vs2[pop[x]]=1;
        }
        x^=a[pop[x]]^b[pop[x]];
        
      }
      v.pb(pm);
    }
    v.pb({});
    for(ll i=0;i<k;i++)if(!vs2[i])v.back().pb(i);
    //for(ll i=0;i<q;i++)cout<<mj[i]<<" ";
    //cout<<v<<flush;
    
    vii v2;
    for(ll i=0;i<v.size();i++){
      v2.pb({v[i].size(),i});
    }
    sort(al(v2));
    ll mr1=v2[0].ss,mr2=v2[1].ss;
    if(mr1>mr2)swap(mr1,mr2);
    //cout<<mr1<<" "<<mr2<<"\n";
    string rs="";
    for(vi i:v)rs.pb('0');
    rs[mr1]=rs[mr2]='1';
    for(ll i=0;i<v.size();i++){
      ll x=i;
      if(x==mr2)x=mr1;
      if(x>mr2)x--;
      string pm=to_bin(x,4);
      if(x==mr1){
        pm.pb('0'+(i!=x));
      }
      for(ll j:v[i])ms[j]=pm;
    }
    for(ll i=0;i<k;i++)rs+=ms[i]+to_bin(mj[i],9);
    
    //cout<<rs<<endl;
    return rs;
}

void answer(const std::vector<int> &e);
string gt(string& st,ll x){
  string rs;
  //if(st.size()<x)cout<<"xd"<<flush;
  for(ll i=0;i<x;i++)rs.pb(st[i]);
  for(ll i=0;i<x;i++)st.erase(st.begin());
  return rs;
}
void bitaro(int n, int m, int q, int k, std::vector<int> a, std::vector<int> b,
std::vector<long long> c, std::vector<int> t, std::vector<int> x,
std::string s){
  for(ll i=0;i<k;i++)zl[x[i]]=i+1;
  vvi v(q+1);
  ll mr1=-1,mr2;
  for(ll i=0;i<=q;i++){
    ll x=to_int(gt(s,1));
    if(x)if(mr1==-1)mr1=i;else mr2=i;
  }
  //cout<<mr1<<" "<<mr2<<"\n"<<flush;
  for(ll i=0;i<k;i++){
    ll x=to_int(gt(s,4));//cout<<x<<" "<<flush;
    if(x>=mr2)x++;
    if(x==mr1)if(to_int(gt(s,1)))x=mr2;
    v[x].pb(i);
    mj[i]=to_int(gt(s,9));
    //cout<<"xd"<<flush;
  }
  //for(ll i=0;i<k;i++)cout<<mj[i]<<" ";cout<<"\n";
  //cout<<v<<"\n";
  for(ll i=0;i<k;i++)pop2[i]=300;
  for(ll i=0;i<q;i++){
    for(ll i=0;i<n;i++)pop[i]=-2;
    for(ll j=0;j<n;j++)g[j].clear();
    while(mj[i]!=300){
      //cout<<mj[i]<<" "<<pop[mj[i]]<<" "<<x[mj[i]];return;
      v[i].pb(x[mj[i]]);
      mj[i]=pop2[mj[i]];
    }
    for(ll j:x)c[j]=1000000000000001LL;
    for(ll j:v[i]){
      g[a[x[j]]].pb(x[j]);
      g[b[x[j]]].pb(x[j]);
      c[x[j]]=0;
      //cout<<x[j]<<" ";
    }
    for(ll j=0;j<m;j++){
      if(!zl[j]){
        g[a[j]].pb(j);g[b[j]].pb(j);
      }
    }
    //for(ll i=0;i<n;i++){cout<<i<<": "<<g[i]<<"\n";}
    priority_queue<pip,vector<pip>,greater<pip>>pq;
    pq.push({0,{0,-1}});
    while(pq.size()){
        pip x=pq.top();
       // cout<<x<<"\n";
        pq.pop();
        if(pop[x.ss.ff]!=-2)continue;
        pop[x.ss.ff]=x.ss.ss;
        for(ll i :g[x.ss.ff]){
            pq.push({x.ff+c[i],{a[i]^b[i]^x.ss.ff,i}});
        }
    }
    vi rs;
    ll pp=-1;
    vector<int> vp;
    while(t[i]){
      vp.pb(pop[t[i]]);
      if(t[i]^a[pop[t[i]]]^b[pop[t[i]]]==0)break;
      if(zl[pop[t[i]]]){
        if(pp!=-1)
        pop2[pp]=zl[pop[t[i]]]-1;
        pp=zl[pop[t[i]]]-1;
      }
      t[i]^=a[pop[t[i]]]^b[pop[t[i]]];
    }
    rev(vp);
    //cout<<vp<<"\n";
    answer(vp);
    
  }

  //cout<<v;
}

• Subtask 1: 0 / 100