結果
問題 | No.332 数列をプレゼントに |
ユーザー | rickytheta |
提出日時 | 2015-12-25 15:57:57 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 1,023 ms / 2,000 ms |
コード長 | 3,297 bytes |
コンパイル時間 | 1,533 ms |
コンパイル使用メモリ | 165,616 KB |
実行使用メモリ | 30,468 KB |
最終ジャッジ日時 | 2023-08-25 21:15:34 |
合計ジャッジ時間 | 11,328 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 43 ms
12,308 KB |
testcase_06 | AC | 103 ms
16,836 KB |
testcase_07 | AC | 184 ms
27,748 KB |
testcase_08 | AC | 100 ms
17,576 KB |
testcase_09 | AC | 4 ms
4,376 KB |
testcase_10 | AC | 6 ms
4,916 KB |
testcase_11 | AC | 55 ms
11,900 KB |
testcase_12 | AC | 191 ms
29,204 KB |
testcase_13 | AC | 121 ms
18,864 KB |
testcase_14 | AC | 27 ms
8,312 KB |
testcase_15 | AC | 159 ms
21,768 KB |
testcase_16 | AC | 145 ms
23,352 KB |
testcase_17 | AC | 192 ms
29,048 KB |
testcase_18 | AC | 1,023 ms
23,356 KB |
testcase_19 | AC | 160 ms
24,136 KB |
testcase_20 | AC | 155 ms
21,612 KB |
testcase_21 | AC | 179 ms
24,812 KB |
testcase_22 | AC | 143 ms
20,136 KB |
testcase_23 | AC | 200 ms
29,848 KB |
testcase_24 | AC | 201 ms
30,468 KB |
testcase_25 | AC | 188 ms
29,836 KB |
testcase_26 | AC | 198 ms
29,956 KB |
testcase_27 | AC | 188 ms
29,764 KB |
testcase_28 | AC | 186 ms
29,788 KB |
testcase_29 | AC | 200 ms
29,672 KB |
testcase_30 | AC | 198 ms
29,816 KB |
testcase_31 | AC | 187 ms
29,652 KB |
testcase_32 | AC | 199 ms
29,708 KB |
testcase_33 | AC | 197 ms
29,808 KB |
testcase_34 | AC | 216 ms
29,724 KB |
testcase_35 | AC | 297 ms
29,916 KB |
testcase_36 | AC | 1 ms
4,380 KB |
testcase_37 | AC | 202 ms
29,660 KB |
testcase_38 | AC | 203 ms
29,960 KB |
testcase_39 | AC | 202 ms
29,788 KB |
testcase_40 | AC | 224 ms
29,828 KB |
testcase_41 | AC | 23 ms
29,684 KB |
testcase_42 | AC | 225 ms
29,800 KB |
testcase_43 | AC | 222 ms
29,724 KB |
testcase_44 | AC | 223 ms
29,992 KB |
testcase_45 | AC | 222 ms
29,680 KB |
testcase_46 | AC | 45 ms
8,648 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef complex<double> P; typedef pair<int,int> pii; #define REP(i,n) for(ll i=0;i<n;++i) #define REPR(i,n) for(ll i=1;i<n;++i) #define FOR(i,a,b) for(ll i=a;i<b;++i) #define DEBUG(x) cout<<#x<<": "<<x<<endl #define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl #define ALL(a) (a).begin(),(a).end() #define MOD (ll)(1e9+7) #define ADD(a,b) a=((a)+(b))%MOD #define FIX(a) ((a)%MOD+MOD)%MOD int main(){ ll n,x; cin>>n>>x; vl a(n); REP(i,n)cin>>a[i]; // 考察は正しかった // 閾値limitを設けて分ける // O(N) // 閾値より大きい奴は組み合わせを全探索してmapにmaskと合わせて突っ込む // O(2^A log 2^A) = O(A 2^A) // 閾値より小さい奴は0-1ナップサックをする 復元ができるように // O(B limit*N) // 合成する // O(limit*N log 2^A) = O(limit*N A) // 復元する ここではmultisetに使用する値を入れていく // 全探索: O(A logN) // ナップサック: O(B limit*N logN) // 出力する 元の数列を見て、multisetにあるかどうかを確認する // O(NlogN) // Bは最悪NなのでNを想定すると // O(A2^A + N^2 limit logN) なお AlogN <= N^2 // Aの最悪はlimitによって、limit^A<=10^100である // A log_10(limit) <= 100 より、A<=100/log_10(limit) // limit = 10^Lとすると、log_10(limit)=Lで、A<=100/L // よって O(100/L 2^(100/L) + N^2 logN 10^L) // これを最小化するLは4.03ぐらい // よって閾値を10^4.03 = 10715にする ll limit = 10715; ll mxval = limit*n; vl more,less; REP(i,n){ if(a[i]>x)continue; if(a[i]>=limit)more.push_back(a[i]); else less.push_back(a[i]); } // 大きい値の全探索 map<ll,ll> XS; REP(mask,1<<more.size()){ ll s = 0; REP(i,more.size()){ if(mask>>i&1)s+=more[i]; } if(s>x)continue; XS[s] = mask; } // 小さい値のナップサック vector< vector<bool> > dp(n+1,vector<bool>(mxval+10,false)); vector< vector<bool> > pred(n+1,vector<bool>(mxval+10,false)); dp[0][0]=true; REP(i,less.size()){ ll cost = less[i]; REP(p,mxval+10){ if(!dp[i][p])continue; dp[i+1][p] = true; pred[i+1][p] = false; if(p+cost<mxval+10){ dp[i+1][p+cost] = true; pred[i+1][p+cost] = true; } } } // 合体 ll ansid = -1; REP(i,min(x+1,mxval+1)){ if(dp[less.size()][i]&&XS.count(x-i)){ ansid = i; break; } } if(ansid==-1){ cout << "No" << endl; return 0; } // 復元 multiset<ll> result; // ここに使う値をぶっこんでいく // dp,predから ll cst = ansid; REP(_i,less.size()){ ll i = less.size()-_i; if(pred[i][cst]){ result.insert(less[i-1]); cst -= less[i-1]; } } assert(cst==0); // 全探索のmaskから ll mask = XS[x-ansid]; REP(i,more.size()){ if(mask>>i&1)result.insert(more[i]); } // 出力 multiset<ll>::iterator iter; REP(i,n){ iter = result.find(a[i]); if(iter!=result.end()){ cout<<"o"; result.erase(iter); }else{ cout<<"x"; } } cout<<endl; return 0; }