Submission #3878888
Source Code Expand
#include <iostream> #include <vector> #include <string> #include <cmath> #include <algorithm> #include <utility> #include <queue> #include <set> #include <map> #include <deque> #include <iomanip> #include <cstdio> #include <stack> using namespace std; typedef long long ll; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<VI> VVI; #define MP make_pair #define PB push_back #define inf 1000000007 #define rep(i,n) for(int i=0;i<(int)(n);++i) vector<ll> a; int main(){ vector<ll> dp(100000); dp[0] = 1; int c = 0; ll k2,k; cin >> k2; k = k2; ll sm = 0; for(int i=1;i<10000;i++){ bool flag = 0; if(i%8!=0){ for(int j=i-1;j>=0;j-=8){ dp[i] += dp[j]; } }else{ dp[i] = 1; } if(i%8==7){ if(dp[i]<(ll)1e18){ if(sm+dp[i]>k){ flag = 1; break; } a.PB(dp[i]); c++; sm += dp[i]; }else{ flag = 1; break; } } if(flag)break; } vector<ll> cnt(c); for(int i=c-1;i>=0;i--){ cnt[i] = (k-sm)/a[i]; k -= a[i]*cnt[i]; cnt[i]++; } // rep(i,c){ // cerr << a[i] << " " << cnt[i] << endl; // } string ans; for(int i=c-1;i>=0;i--){ for(int j=0;j<cnt[i];j++){ ans += "F"; } ans +="ESTIVAL"; } cerr <<ans.size() << endl; if(ans.size()<=5000){ cout << ans << endl; }else{ rep(i,20000)dp[i] = 0; rep(i,8)dp[i] = 1; vector<ll> s(8,1); c= 0; a.clear(); for(int i=8;i<20000;i++){ bool flag = 0; if((i-8)%16!=0&&(i-8)%16!=9){ int pp = ((i-8)%16)/2; dp[i] = s[pp-1]; s[pp] += dp[i]; }else{ dp[i] = 1; int pp = ((i-8)%16)/2; s[pp]++; } if((i-8)%16==15){ if(dp[i]<(ll)1e18){ if(sm+dp[i]>k2){ flag = 1; break; } a.PB(dp[i]); c++; sm += dp[i]; }else{ flag = 1; break; } } if(flag)break; } vector<ll>cnt2(c); for(int i=c-1;i>=0;i--){ cnt2[i] = (k-sm)/a[i]; k2 -= a[i]*cnt2[i]; cnt2[i]++; } string ans2; for(int i=c-1;i>=1;i--){ for(int j=0;j<cnt[i];j++){ ans2 += "F"; } ans2 +="EESSTTIIVVAALL"; } //cerr << ans2.size() << endl; cout << ans2 << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | G - FESTIVAL |
User | mtsd |
Language | C++14 (Clang 3.8.0) |
Score | 0 |
Code Size | 3080 Byte |
Status | WA |
Exec Time | 2 ms |
Memory | 1024 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1000 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0.txt, example1.txt |
All | 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, example0.txt, example1.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
000.txt | AC | 2 ms | 1024 KB |
001.txt | AC | 2 ms | 1024 KB |
002.txt | AC | 2 ms | 1024 KB |
003.txt | AC | 2 ms | 1024 KB |
004.txt | AC | 2 ms | 1024 KB |
005.txt | AC | 2 ms | 1024 KB |
006.txt | AC | 2 ms | 1024 KB |
007.txt | AC | 2 ms | 1024 KB |
008.txt | AC | 2 ms | 1024 KB |
009.txt | AC | 2 ms | 1024 KB |
010.txt | AC | 2 ms | 1024 KB |
011.txt | AC | 2 ms | 1024 KB |
012.txt | AC | 2 ms | 1024 KB |
013.txt | AC | 2 ms | 1024 KB |
014.txt | AC | 2 ms | 1024 KB |
015.txt | AC | 2 ms | 1024 KB |
016.txt | AC | 2 ms | 1024 KB |
017.txt | WA | 2 ms | 1024 KB |
018.txt | WA | 2 ms | 1024 KB |
019.txt | WA | 2 ms | 1024 KB |
020.txt | WA | 2 ms | 1024 KB |
021.txt | WA | 2 ms | 1024 KB |
022.txt | WA | 2 ms | 1024 KB |
023.txt | WA | 2 ms | 1024 KB |
024.txt | WA | 2 ms | 1024 KB |
025.txt | WA | 2 ms | 1024 KB |
026.txt | WA | 2 ms | 1024 KB |
027.txt | WA | 2 ms | 1024 KB |
028.txt | WA | 2 ms | 1024 KB |
029.txt | WA | 2 ms | 1024 KB |
030.txt | WA | 2 ms | 1024 KB |
031.txt | WA | 2 ms | 1024 KB |
032.txt | WA | 2 ms | 1024 KB |
033.txt | WA | 2 ms | 1024 KB |
034.txt | AC | 2 ms | 1024 KB |
035.txt | AC | 2 ms | 1024 KB |
036.txt | AC | 2 ms | 1024 KB |
037.txt | AC | 2 ms | 1024 KB |
038.txt | WA | 2 ms | 1024 KB |
039.txt | WA | 2 ms | 1024 KB |
040.txt | WA | 2 ms | 1024 KB |
041.txt | WA | 2 ms | 1024 KB |
042.txt | WA | 2 ms | 1024 KB |
043.txt | WA | 2 ms | 1024 KB |
044.txt | WA | 2 ms | 1024 KB |
045.txt | WA | 2 ms | 1024 KB |
046.txt | WA | 2 ms | 1024 KB |
047.txt | WA | 2 ms | 1024 KB |
048.txt | WA | 2 ms | 1024 KB |
049.txt | WA | 2 ms | 1024 KB |
050.txt | AC | 2 ms | 1024 KB |
051.txt | WA | 2 ms | 1024 KB |
052.txt | AC | 2 ms | 1024 KB |
053.txt | AC | 2 ms | 1024 KB |
example0.txt | AC | 2 ms | 1024 KB |
example1.txt | AC | 2 ms | 1024 KB |