結果
問題 | No.252 "良問"(良問とは言っていない (2) |
ユーザー |
![]() |
提出日時 | 2015-09-24 22:19:41 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 1,867 bytes |
コンパイル時間 | 755 ms |
コンパイル使用メモリ | 83,676 KB |
実行使用メモリ | 51,176 KB |
最終ジャッジ日時 | 2024-07-19 09:05:04 |
合計ジャッジ時間 | 1,586 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:91:49: warning: ‘pmin’ may be used uninitialized in this function [-Wmaybe-uninitialized] 91 | ans=min(ans,gmin+pmin); | ~~~~^~~~~
ソースコード
#include <iostream>#include <cmath>#include <climits>#include <string>#include <vector>#include <queue>#include <stack>#include <functional>#include <algorithm>#include <sstream>#include <map>#include <set>#include <utility>#define endl '\n'#define ALL(a) (a).begin(),(a).end()#define SZ(a) int((a).size())#define FOR(i,a,b) for(int i=(a);i<(b);++i)#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)#define REP(i,n) FOR(i,0,n)#define RREP(i,n) for (int i=(n)-1;i>=0;i--)#define DEBUG(x) cout<<#x<<": "<<x<<endlusing namespace std;typedef pair<int,int> P;typedef long long int LL;const int INF=100000000;const string good="good",problem="problem";string s[1000000];int main(){ios::sync_with_stdio(false);cin.tie(0);int t;cin>>t;REP(i,t) cin>>s[i];REP(i,t){int ans=INF;int n=SZ(s[i]);vector<int> cg(n,INF);vector<int> cp(n,INF);vector<int> cgi(n);vector<int> cpi(n);REP(j,n-4+1){int c=0;REP(k,4){if(s[i][j+k]!=good[k]) c++;}cg[j]=c;if(j!=0){if(c==0) cgi[j]=cgi[j]+1;else cgi[j]=cgi[j];}else{if(c==0) cgi[j]=1;else cgi[j]=0;}}REP(j,n-7+1){int c=0;REP(k,7){if(s[i][j+k]!=problem[k]) c++;}cp[j]=c;if(j!=0){if(c==0) cpi[j]=cpi[j-1]+1;else cpi[j]=cpi[j-1];}else{if(c==0) cpi[j]=1;else cpi[j]=0;}}vector<int> co(7+1,0);FOR(i,4,n-7+1){co[cp[i]]++;}int gmin=INF;int pmin;REP(i,8){if(co[i]!=0){pmin=i;break;}}REP(i,n-11+1){gmin=min(gmin,cg[i]);//DEBUG(pmin);if(i<7){ans=min(ans,gmin+pmin);}else{//DEBUG(cpi[i-7]);ans=min(ans,gmin+pmin+cpi[i-7]);}co[cp[i+4]]--;if(cp[i+4]==pmin&&co[pmin]==0){REP(l,8){if(co[l]!=0){pmin=l;break;}}}}cout<<ans<<endl;}return 0;}