#1099791 (C++17) No.382 シャイな人たち (2)

提出ソース
結果

問題	No.382 シャイな人たち (2)
ユーザー	soryuusi0219
提出日時	2025-06-19 18:46:44
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	2,111 ms / 8,000 ms
コード長	13,512 bytes
コンパイル時間	3,071 ms
コンパイル使用メモリ	226,120 KB
実行使用メモリ	20,864 KB
最終ジャッジ日時	2025-06-19 18:47:26
合計ジャッジ時間	41,448 ms
ジャッジサーバーID （参考情報）	judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 21
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
#define GET4(_1,_2,_3,NAME,...) NAME
#define GET5(_1,_2,_3,_4,NAME,...) NAME
#define GET6(_1,_2,_3,_4,_5,NAME,...) NAME
#define GET11(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NAME,...) NAME
#define rep1(i, n)  for(long long i=0;i<(long long)(n);i++)
#define rep2(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define rep3(i,k,n,s) for(long long i=k;i<(long long)(n);i+=(s))
#define rep(...) GET5(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define per1(i,n) for(long long i=(n)-1ll;i>-1ll;i--)
#define per2(i,k,n) for(long long i=(n)-1ll;i>(long long)(k)-1ll;i--)
#define per3(i,k,n,s) for(long long i=(n)-1ll;i>(long long)(k)-1ll;i-=(s))
#define per(...) GET5(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define ub(v,k) (upper_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define readi1(n0) ll n0; cin >> (n0);
#define readi2(n0,n1) ll n0,n1; cin >> (n0) >> (n1);
#define readi3(n0,n1,n2) ll n0,n1,n2; cin >> (n0) >> (n1) >> (n2);
#define readi4(n0,n1,n2,n3) ll n0,n1,n2,n3; cin >> (n0) >> (n1) >> (n2) >> (n3);
#define readi5(n0,n1,n2,n3,n4) ll n0,n1,n2,n3,n4; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4);
#define readi6(n0,n1,n2,n3,n4,n5) ll n0,n1,n2,n3,n4,n5; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4) >> (n5);
#define readi7(n0,n1,n2,n3,n4,n5,n6) ll n0,n1,n2,n3,n4,n5,n6; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4) >> (n5) >> (n6);
#define readi8(n0,n1,n2,n3,n4,n5,n6,n7) ll n0,n1,n2,n3,n4,n5,n6,n7; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4) >> (n5) >> (n6) >> (n7);
#define readi9(n0,n1,n2,n3,n4,n5,n6,n7,n8) ll n0,n1,n2,n3,n4,n5,n6,n7,n8; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4) >> (n5) >> (n6) >> (n7) >> (n8);
#define readi10(n0,n1,n2,n3,n4,n5,n6,n7,n8,n9) ll n0,n1,n2,n3,n4,n5,n6,n7,n8,n9; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4) >> (n5) >> (n6) >> (n7) >> (n8) >> (n9);
#define readi(...) GET11(__VA_ARGS__, readi10, readi9, readi8, readi7, readi6, readi5, readi4, readi3, readi2, readi1)(__VA_ARGS__)
#define readvi1(v,n) vi v(n); rep(i,(n)) cin >> (v).at(i);
#define readvi2(v,w,n) vi v(n),w(n); rep(i,(n)) cin >> (v).at(i) >> (w).at(i);
#define readvi3(v,w,x,n) vi v(n),w(n),x(n); rep(i,(n)) cin >> (v).at(i) >> (w).at(i) >> (x).at(i);
#define readvi4(v,w,x,y,n) vi v(n),w(n),x(n),y(n); rep(i,(n)) cin >> (v).at(i) >> (w).at(i) >> (x).at(i) >> (y).at(i);
#define readvi(...) GET5(__VA_ARGS__, readvi3, readvi2, readvi1)(__VA_ARGS__)
#define reads1(n) string n; cin >> (n);
#define reads2(n,m) string n,m; cin >> (n) >> (m);
#define reads3(n,m,l) string n,m,l; cin >> (n) >> (m) >> (l);
#define reads4(n,m,l,k) string n,m,l; cin >> (n) >> (m) >> (l) >> (k);
#define reads(...) GET5(__VA_ARGS__, reads4, reads3, reads2, reads1)(__VA_ARGS__)
#define readvs(v,n) vs v(n); rep(i,(n)) cin >> (v).at(i);
#define readd1(n) ld n; cin >> (n);
#define readd2(n,m) ld n,m; cin >> (n) >> (m);
#define readd3(n,m,l) ld n,m,l; cin >> (n) >> (m) >> (l);
#define readd4(n,m,l,k) ld n,m,l; cin >> (n) >> (m) >> (l) >> (k);
#define readd(...) GET5(__VA_ARGS__, readd4, readd3, readd2, readd1)(__VA_ARGS__)
#define readvvi(v,n,m) vvi v((n),vi(m)); rep(i,(n))rep(j,(m)) cin >> (v).at(i).at(j);
#define readvvs(v,n,m) vvs v((n),vs(m)); rep(i,(n))rep(j,(m)) cin >> (v).at(i).at(j);
#define readvpi(v,n) vpi v(n); rep(i,(n)) cin >> (v).at(i).fi >> (v).at(i).se;
#define readg(G,n,m) vvi G(n);rep(i,m){readi(a,b);a--;b--;G.at(a).push_back(b);G.at(b).push_back(a);}
#define readgd(G,n,m) vvi G(n);rep(i,m){readi(a,b);a--;b--;G.at(a).push_back(b);}
#define readgdrev(G,n,m) vvi G(n);rep(i,m){readi(a,b);a--;b--;G.at(b).push_back(a);}
#define readt(G,n) vvi G(n);rep(i,n-1){readi(a,b);a--;b--;G.at(a).push_back(b);G.at(b).push_back(a);}
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template<class T> using P = pair<T,T>;
template<class T> using PP = tuple<T,T,T>;
template<class T> using PPP = tuple<T,T,T,T>;
using pi = P<ll>;
using ppi = PP<ll>;
using pppi = PPP<ll>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T> using VVV = vector<vector<vector<T>>>;
template<class T> using VVVV = vector<vector<vector<vector<T>>>>;
using vi=V<ll>;
using vvi=VV<ll>;
using vvvi=VVV<ll>;
using vvvvi=VVVV<ll>;
using vpi=V<pi>;
using vvpi=VV<pi>;
using vppi=V<ppi>;
using vvppi=VV<ppi>;
using vpppi=V<pppi>;
using vvpppi=VV<pppi>;
using vb=V<bool>;
using vvb=VV<bool>;
using vs=V<string>;
using vvs=VV<string>;
const ll inf=(1 << 30);
const ll Inf=((ll)1 << 40);
const ll INf=((ll)1 << 50);
const ll INF=((ll)1 << 60);
const double eps=1e-10;
/////////////////////////////////////////////////////////
template<class T> using PQ = priority_queue<T>;
template<class T> using SPQ = priority_queue<T,vector<T>,greater<T>>;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
void out0(ll a){cout<<a;}
void out0(unsigned int a){cout<<a;}
void out0(int a){cout<<a;}
void out0(long int a){cout<<a;}
void out0(long unsigned int a){cout<<a;}
void out0(unsigned long long a){cout<<a;}
void out0(char a){cout<<a;}
void out0(char* a){cout<<a;}
void out0(string a){cout<<a;}
void out0(float a){cout<<fixed<<setprecision(15)<<a;}
void out0(double a){cout<<fixed<<setprecision(15)<<a;}
void out0(ld a){cout<<fixed<<setprecision(15)<<a;}
template<class T> void out0s(T a);
template<class T1, class T2> void out0(pair<T1,T2> p){out0s(p.fi); out0s(p.se);}
template < typename Tuple, size_t ...I >
array<int,sizeof...(I)>
tuple_print(Tuple&& t, index_sequence<I...>){
  return {{ (void( out0s(get<I>(t))), 0)... }};
}
template<class... T> void out0(tuple<T...> p){
  tuple_print(p,
  make_index_sequence<tuple_size<decay_t<tuple<T...>>>::value>{});
}
template<class T> void out0(vector<T> v){for(T c : v) out0s(c);}
template<class T> void out0(set<T> v){for(T c : v) out0s(c);}
template<class T> void out0s(T a){out0(a); cout << " ";}
template<class T> void out(VV<T> v){for(auto c : v) {out0(c); cout << endl;}}
template<class S, class T> void out(map<S,T> v){for(auto c : v) {out0(c); cout << endl;}}
template<class T>void out(T a) {out0(a); cout << endl;}
template<class T, class... Ts>void out(T a, Ts... b) {out0(a); cout << " "; out(b...);}
void out0d(ll a){cout<<a;}
void out0d(int a){cout<<a;}
void out0d(unsigned int a){cout<<a;}
void out0d(long unsigned int a){cout<<a;}
void out0d(long int a){cout<<a;}
void out0d(unsigned long long a){cout<<a;}
void out0d(char a){cout<<a;}
void out0d(char* a){cout<<a;}
void out0d(string a){cout<<a;}
void out0d(float a){cout<<fixed<<setprecision(15)<<a;}
void out0d(double a){cout<<fixed<<setprecision(15)<<a;}
void out0d(ld a){cout<<fixed<<setprecision(15)<<a;}
template<class T> void out0sd(T a);
template<class T1, class T2> void out0d(pair<T1,T2> p){cout << "("; out0sd(p.fi); out0d(p.se); cout << ")";}
template < typename Tuple, size_t ...I >
array<int,sizeof...(I)>
tuple_printd(Tuple&& t, index_sequence<I...>){
  return {{ (void( out0s(get<I>(t))), 0)... }};
}
template<class... T> void out0d(tuple<T...> p){
  cout << "(";
  tuple_printd(p,
  make_index_sequence<tuple_size<decay_t<tuple<T...>>>::value>{});
  cout << ")";
}
template<class T> void out0d(vector<T> v){for(T c : v) out0sd(c);}
template<class T> void out0d(set<T> v){for(T c : v) out0sd(c);}
template<class T> void out0sd(T a){out0d(a); cout << " ";}
template<class T> void outd(VV<T> v){for(auto c : v) {out0d(c); cout << endl;}}
template<class S, class T> void outd(map<S,T> v){for(auto c : v) {out0d(c); cout << endl;}}
template<class T>void outd(T a) {out0d(a); cout << endl;}
template<class T, class... Ts>void outd(T a, Ts... b) {out0d(a); cout << " "; outd(b...);}
template<class T> void outm(T a){cout<<a.val()<<'\n';}
template<class T> void outvm(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i].val();}cout<<'\n';}
template<class T> void outvvm(T v){rep(i,v.size())outvm(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void posimp(T b){if(b)out("possible");else out("impossible");}
template<class T> void PosImp(T b){if(b)out("Possible");else out("Impossible");}
template<class T> void POSIMP(T b){if(b)out("POSSIBLE");else out("IMPOSSIBLE");}
void outs(ll a,ll b,ll i){if(abs(a)>=i-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return (a / gcd(a,b)) * b;}
ll powll(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a;a=a*a;b>>=1;}return res;}
ll modpow(ll a,ll b,ll modd){ll res=1;a%=modd;while(b){if(b&1)res=res*a%modd;a=a*a%modd;b>>=1;}return res;}
ll sqrtll(ll a){assert(a >= 0); ll r = (ll)sqrtl((ld)a)-1; while(r < 0 || (r+1)*(r+1) <= a) r++; return r;}
ll cbrtll(ll a){assert(a >= 0); ll r = (ll)cbrtl((ld)a)-1; while(r < 0 || (r+1)*(r+1)*(r+1) <= a) r++; return r;}
ll modinv(ll a, ll b){assert(a); if(a == 1) return 1; if(b == 1) return 0; ll ret = (1ll-b*modinv(b%a, a))/a; ret %= b; if(ret < 0) ret += b; return ret;}

vi maximal_independent_set(vvi& G){
  static constexpr int MAX = 128;
  ll n = G.size();
  assert(n <= MAX);
  const ll M = (ld)n * 0.0869l;
  if(n <= 64){
    vector<ull> nbh(n);
    rep(i,n)for(auto j:G.at(i)) nbh[i] |= (1ull << j);
    unordered_map<ull,pair<ll,ull>> memo;
    function<pair<ll,ull>(ull)> rec = [&](ull x){
      ll degmax = -1, vmax = -1;
      ull y = x;
      ll ret = 0;
      ull rets = 0;
      while(y){
        ll v = __builtin_ctzll(y);
        y &= ~(1ull << v);
        if(!(nbh[v] & x)) ret++, x &= ~(1ull << v), rets |= (1ull << v);
        ll deg = __builtin_popcountll(nbh[v] & x);
        if(deg == 1) {
          ll w = __builtin_ctzll(nbh[v] & x);
          auto [cret, crets] = rec(x & ~(1ull << v) & ~(1ull << w));
          return make_pair(ret + cret + 1, rets | crets | (1ull << v));
        }
        if(chmax(degmax,deg)) vmax = v;
      }
      if(memo.count(x)) return make_pair(ret + memo[x].fi, rets + memo[x].se);
      if(!x) return make_pair(ret, rets);
      ull z = x & ~(1ull << vmax);
      auto [cret1, crets1] = rec(z);
      if(degmax > 2){
        auto [cret2, crets2] = rec(z & ~nbh[vmax]);
        if(chmax(cret1, cret2 + 1)) crets1 = crets2 | (1ull << vmax);
      }
      if(__builtin_popcountll(x) <= M) memo[x] = {cret1, crets1};
      return  make_pair(ret + cret1, rets + crets1);
    };
    auto [_, ansset] = rec(n == 64 ? ~(0ull) : (1ull << n)-1);
    vi ret;
    while(ansset){
      ll v = __builtin_ctzll(ansset);
      ansset &= ~(1ull << v);
      ret.push_back(v);
    }
    return ret;
  }
  else{
    vector<__uint128_t> nbh(n);
    rep(i,n)for(auto j:G.at(i)) nbh[i] |= (((__uint128_t)1) << j);
    map<__uint128_t,pair<ll,__uint128_t>> memo;
    auto ctzint128 = [&](__uint128_t x){
      if((ull)x) return __builtin_ctzll((ull)x);
      return __builtin_ctzll((ull)(x >> 64)) + 64;
    };
    auto popcountint128 = [&](__uint128_t x){
      return __builtin_popcountll((ull)x) +  __builtin_popcountll((ull)(x >> 64));
    };
    function<pair<ll,__uint128_t>(__uint128_t)> rec = [&](__uint128_t x){
      ll degmax = -1, vmax = -1;
      __uint128_t y = x;
      ll ret = 0;
      __uint128_t rets = 0;
      while(y){
        ll v = ctzint128(y);
        y &= ~(((__uint128_t)1) << v);
        if(!(nbh[v] & x)) ret++, x &= ~(((__uint128_t)1) << v), rets |= (((__uint128_t)1) << v);
        ll deg = popcountint128(nbh[v] & x);
        if(deg == 1) {
          ll w = ctzint128(nbh[v] & x);
          auto [cret, crets] = rec(x & ~(((__uint128_t)1) << v) & ~(((__uint128_t)1) << w));
          return make_pair(ret + cret + 1, rets | crets | (((__uint128_t)1) << v));
        }
        if(chmax(degmax,deg)) vmax = v;
      }
      if(memo.count(x)) return make_pair(ret + memo[x].fi, rets + memo[x].se);
      if(!x) return make_pair(ret, rets);
      __uint128_t z = x & ~(((__uint128_t)1) << vmax);
      auto [cret1, crets1] = rec(z);
      if(degmax > 2){
        auto [cret2, crets2] = rec(z & ~nbh[vmax]);
        if(chmax(cret1, cret2 + 1)) crets1 = crets2 | (((__uint128_t)1) << vmax);
      }
      if(popcountint128(x) <= M) memo[x] = {cret1, crets1};
      return  make_pair(ret + cret1, rets + crets1);
    };
    auto [_, ansset] = rec(n == 128 ? ~((__uint128_t)0) : (((__uint128_t)1) << n)-1);
    vi ret;
    while(ansset){
      ll v = ctzint128(ansset);
      ansset &= ~(((__uint128_t)1) << v);
      ret.push_back(v);
    }
    return ret;
  }
}



int main(){
  constexpr ll A = 12345;
  constexpr ll M = 1000003;
  readi(s);
  s = (s*A) % M;
  ll n = (s % 120)+2;
  s = (s*A) % M;
  ll p = s;
  vvi G(n);
  rep(i,n)rep(j,i+1,n){
    s = (s*A) % M;
    if(s >= p){
      G.at(i).push_back(j);
      G.at(j).push_back(i);
    }
  }
  auto v = maximal_independent_set(G);
  if(v.size() == n){ cout << -1 << endl; return 0;}
  cout << v.size()+1 << endl;
  rep(i,v.size()){
    cout << v.at(i)+1;
    if(i < v.size()-1) cout << " ";
  }
  cout << endl;
}
yukicoder

結果

ソースコード
