Submission #1241005
Source Code Expand
#include<algorithm> #include<vector> #include<list> #include<iostream> #include<utility> #include<string> #include<set> #include<queue> #include<stack> #include<iterator> #include<map> #include<limits> #include<iomanip> const int INF=2147483647; using namespace std; long long tautCt(long long n){ if(n<=1) return 0; vector<long long> ncr(n+1); ncr[0]=1; for(int i=1; i<=n; i++){ ncr[i]=ncr[i-1]*(n+1-i)/i; //cout<<ncr[i]<<endl; } long long ans=0; for(int i=2; i<=n; i+=2){ ans+=ncr[i]; } return ans; } long long tautCt2(long long n){ vector<long long> ncr(n+1); ncr[0]=1; for(int i=1; i<=n; i++){ ncr[i]=ncr[i-1]*(n+1-i)/i; //cout<<ncr[i]<<endl; } long long ans=0; for(int i=0; i<=n; i++){ ans+=ncr[i]*ncr[i]; } return ans; } long long tautCt2(long long m, long long n){ if(m>n) return tautCt2(n,m); vector<long long> ncr(n+1), mcr(n+1); ncr[0]=1; mcr[0]=1; for(int i=1; i<=n; i++){ ncr[i]=ncr[i-1]*(n+1-i)/i; //cout<<ncr[i]<<endl; } for(int i=1; i<=m; i++){ mcr[i]=mcr[i-1]*(m+1-i)/i; } long long ans=0; for(int i=0; i<=m; i++){ ans+=mcr[i]*ncr[i]; } return ans; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); long long n; cin>>n; vector<long long> tauts(51), tauts2(51); vector<vector<long long>> tauts2b(51,vector<long long>(51,0ll)); for(int i=0; i<=50; i++){ tauts[i]=tautCt(i); tauts2[i]=tautCt2(i); } //cout<<tauts[50]; for(int i=0; i<=50; i++){ for(int j=0; j<=50; j++){ tauts2b[i][j]=tautCt2(i,j); } } //int cur=1; auto it=lower_bound(tauts.begin(),tauts.end(), n); if(*it>n) it--; long long cand1=*it; int num=(it-tauts.begin()); n-=*it; list<int> ans(num,1); int cur=2; while(n){ auto it=ans.begin(); int i; for(i=0; tauts2b[i][num-i]<=n;i++,it++){} it--; i--; if(it==ans.begin()) ans.push_front(cur); else ans.insert(it,cur); ans.push_back(cur); n-=tauts2b[i][num-i]; cur++; } /* while(n){ auto it=lower_bound(tauts.begin(),tauts.end(), n); if(*it>n) it--; long long cand1=*it; int num=(it-tauts.begin()); long long cand2=0; int num1=100, num2=100; for(int i=1; tauts[i]<n; i++){ for(int j=1; j<=i; j++){ long long tot=tauts[i+j]+tauts2b[i][j]; if(tot<=n && tot>cand2 || tot==cand2 && i+j<num1+num2){ cand2=tot; num1=j; num2=i; } } } int pos=0; while(n>tauts[2*pos]+tauts2[pos]){ pos++; } if(n!=tauts[2*pos]+tauts2[pos]) pos--; cand2=tauts[2*pos]+tauts2[pos]; if(cand2>cand1 && num1+num2+1<=num){ n-=cand2; for(int i=0; i<num1; i++){ ans.push_back(cur); } ans.push_back(cur+1); for(int i=0; i<num2; i++){ ans.push_back(cur); } ans.push_back(cur+1); cur+=2; } else{ n-=*it; for(int i=0; i<num; i++){ ans.push_back(cur); } cur++; } cout<<n<<endl; } */ cout<<ans.size()<<endl; for(int i:ans){ cout<<i<<" "; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Tautonym Puzzle |
User | usernameson |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3979 Byte |
Status | RE |
Exec Time | 2224 ms |
Memory | 1781120 KB |
Judge Result
Set Name | Sample | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1000 | ||||||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt |
All | 00_example_01.txt, 00_example_02.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 4 ms | 256 KB |
00_example_02.txt | AC | 4 ms | 256 KB |
01.txt | TLE | 2176 ms | 1182336 KB |
02.txt | AC | 4 ms | 256 KB |
03.txt | WA | 4 ms | 256 KB |
04.txt | TLE | 2224 ms | 1780608 KB |
05.txt | AC | 4 ms | 256 KB |
06.txt | AC | 4 ms | 256 KB |
07.txt | TLE | 2224 ms | 1781120 KB |
08.txt | TLE | 2185 ms | 1170560 KB |
09.txt | AC | 4 ms | 256 KB |
10.txt | AC | 4 ms | 256 KB |
11.txt | RE | 123 ms | 256 KB |
12.txt | AC | 4 ms | 256 KB |
13.txt | AC | 4 ms | 256 KB |
14.txt | AC | 4 ms | 256 KB |
15.txt | WA | 4 ms | 384 KB |
16.txt | AC | 4 ms | 256 KB |
17.txt | AC | 4 ms | 256 KB |
18.txt | WA | 4 ms | 256 KB |
19.txt | AC | 4 ms | 256 KB |
20.txt | AC | 4 ms | 256 KB |
21.txt | WA | 11 ms | 2176 KB |
22.txt | AC | 4 ms | 256 KB |
23.txt | TLE | 2185 ms | 1174784 KB |
24.txt | WA | 4 ms | 256 KB |
25.txt | WA | 4 ms | 256 KB |
26.txt | RE | 100 ms | 256 KB |
27.txt | TLE | 2188 ms | 1126912 KB |
28.txt | AC | 4 ms | 256 KB |
29.txt | RE | 100 ms | 256 KB |
30.txt | RE | 102 ms | 256 KB |