結果
問題 |
No.382 シャイな人たち (2)
|
ユーザー |
|
提出日時 | 2025-06-19 18:40:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 13,444 bytes |
コンパイル時間 | 3,947 ms |
コンパイル使用メモリ | 305,908 KB |
実行使用メモリ | 20,864 KB |
最終ジャッジ日時 | 2025-06-19 18:41:29 |
合計ジャッジ時間 | 43,521 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 21 |
ソースコード
#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); cout << v.size()+1 << endl; rep(i,v.size()){ cout << v.at(i)+1; if(i < v.size()-1) cout << " "; } }