fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define str string
  4. #define FOR(i,k,l) for(int i=l;i<=k;i++)
  5. #define FOD(i,k,l) for(int i=l;i>=k;i--)
  6. using namespace std;
  7. str k;
  8. ll n,m,a[1000],g[1000],g1[1000];
  9. const int BASE = 1000;
  10. typedef vector <ll> big;
  11. big INT(str s) {
  12.     big a;
  13.     if (s.size() == 0)
  14.     {
  15.         a.push_back(0);
  16.         return a;
  17.     }
  18.     while (s.size()%3!=0) s='0'+s;
  19.     for (int i=0; i<(ll)s.size();i+=log10(BASE))
  20.     {
  21.         ll r = 0;
  22.         FOR(j,log10(BASE)-1,0)
  23.         r=r*10+(s[i+j]-'0');
  24.         a.insert(a.begin(),r);
  25.     }
  26.     return a;
  27. }
  28.  
  29. ll SS (big a,big b)
  30. {
  31.     ll c=a.size()-1;
  32.     ll d=b.size()-1;
  33.     if(c<d) return 1;
  34.     else if(c==d)
  35.     {
  36.         FOD(i,0,c)
  37.         {
  38.             if(a[i]<b[i]) return 1;
  39.             else if(a[i]>b[i]) return 0;
  40.         }
  41.     }
  42.     return 1;
  43. }
  44. big Cong (big a, big b) {
  45.     big c;
  46.     ll v=a.size();
  47.     ll u=b.size();
  48.     ll Max = max(v, u)-1;
  49.     ll nho = 0;
  50.     FOR(i,Max,0)
  51.     {
  52.         ll x = nho;
  53.         if (i<v) x += a[i];
  54.         if (i<u) x += b[i];
  55.         ll r = x % BASE;
  56.         c.push_back(r);
  57.         nho = x / BASE;
  58.     }
  59.     if (nho > 0) c.push_back(nho);
  60.     ll z=c.size()-1;
  61.     FOD(i,1,z)
  62.     {
  63.         if(c[i]==0) c.pop_back();
  64.         else break;
  65.     }
  66.     return c;
  67. }
  68. big Tru (big a, big b) {
  69.     big c;
  70.     ll v=a.size();
  71.     ll u=b.size();
  72.     ll Max = max(v, u)-1;
  73.     ll nho = 0;
  74.     FOR(i,Max,0)
  75.     {
  76.         ll x=0;
  77.         if (i<v) x += a[i];
  78.         if (i<u) x -= b[i];
  79.         x-=nho;
  80.         nho=0;
  81.         while (x<0) {x+=BASE;nho++;}
  82.         c.push_back(x);
  83.     }
  84.     ll z=c.size()-1;
  85.     FOD(i,1,z)
  86.     {
  87.         if(c[i]==0) c.pop_back();
  88.         else break;
  89.     }
  90.     return c;
  91. }
  92. big Nhan1 (big a,ll b)
  93. {
  94.     ll d=a.size()-1;
  95.     big c;
  96.     ll nho=0;
  97.     FOR(i,d,0)
  98.     {
  99.         ll x=a[i]*b+nho;
  100.         nho=x/BASE;
  101.         x=x%BASE;
  102.         c.push_back(x);
  103.     }
  104.     if(nho>0) c.push_back(nho);
  105.     else
  106.     {
  107.         ll z=c.size()-1;
  108.         FOD(i,1,z)
  109.         {
  110.             if(c[i]==0) c.pop_back();
  111.             else break;
  112.         }
  113.     }
  114.     return c;
  115. }
  116. big Nhan2 (big a, big b) {
  117.     ll e=a.size()-1;
  118.     ll f=b.size()-1;
  119.     big c(e+f+2);
  120.     FOR(i,f,0)
  121.     {
  122.         big d=Nhan1(a,b[i]);
  123.         ll q=d.size()-1;
  124.         FOR(j,q,0)
  125.             c[i+j]+=d[j];
  126.         ll nho = 0;
  127.         ll zz=c.size()-1;
  128.         FOR(j,zz,i)
  129.         {
  130.             ll x = nho + c[j];
  131.             c[j] = x % BASE;
  132.             nho = x / BASE;
  133.         }
  134.         if (nho > 0) c.push_back(nho);
  135.     }
  136.     while (!c.empty() && c.back() == 0) c.pop_back();
  137.     return c;
  138. }
  139. void xuat(big a)
  140. {
  141.     ll l = a.size()-1;
  142.     cout<<a[l];
  143.     FOD(i,0,l-1) cout << setfill('0') << setw(3) << a[i];
  144.     cout<<"\n";
  145. }
  146. int main()
  147. {
  148.     //freopen("inp","r",stdin);
  149.     //freopen("out","w",stdout);
  150.     cin>>n>>m;
  151.     cin>>k;
  152.     big v=INT(k);
  153.     FOR(i,m,1)
  154.     cin>>a[i];
  155.     big f[1000];
  156.     f[0].push_back(1);
  157.     FOR(i,m-1,1)
  158.     f[i]=Nhan1(f[i-1],n-m+i);
  159.     FOR(i,m,1)
  160.     {
  161.         ll s=1;
  162.         while(SS(v,f[m-i])==0)
  163.         {
  164.             v=Tru(v,f[m-i]);
  165.             while(g[s]==1) s++;
  166.             s++;
  167.         }
  168.         while(g[s]==1) s++;
  169.         g[s]=1;
  170.         cout<<s<<" ";
  171.     }
  172.     big x;
  173.     FOR(i,m,1)
  174.     {
  175.         ll s=0;
  176.         FOR(j,a[i]-1,1)
  177.         {
  178.             if(g1[j]==0) s++;
  179.         }
  180.         big xx=Nhan1(f[m-i],s);
  181.         x=Cong(x,xx);
  182.         g1[a[i]]=1;
  183.     }
  184.     big o={1};
  185.     cout<<"\n";
  186.     xuat(Cong(x,o));
  187.     return 0;
  188. }
  189.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/ci93Qs
problem SHCH, based on SPOJ submission 33978047 (CPP14-CLANG), 2024-12-17 15:04:00
language:
C++14 (clang 8.0)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!