fork download
copy 
  1. #include <bits/stdc++.h>
  2. /*
  3.         penguin yes cop code
  4.         https://c...content-available-to-author-only...s.com/profile/Tuanhaiphong2
  5. */
  6. using namespace std;
  7. #define x1 o1
  8. #define x2 o2
  9. #define y1 o3
  10. #define y2 o4
  11. #define ll long long
  12. #define fi first
  13. #define se second
  14. #define MOD 1000000007
  15. const int base = 1000000000; const int base_digits = 9;
  16. struct bigint {
  17.     vector<int> a; int sign;
  18.  
  19.     bigint() :
  20.         sign(1) {
  21.     }
  22.  
  23.     bigint(long long v) {
  24.         *this = v;
  25.     }
  26.  
  27.     bigint(const string &s) {
  28.         read(s);
  29.     }
  30.  
  31.     void operator=(const bigint &v) {
  32.         sign = v.sign;
  33.         a = v.a;
  34.     }
  35.  
  36.     void operator=(long long v) {
  37.         sign = 1;
  38.         if (v < 0)
  39.             sign = -1, v = -v;
  40.         for (; v > 0; v = v / base)
  41.             a.push_back(v % base);
  42.     }
  43.  
  44.     bigint operator+(const bigint &v) const {
  45.         if (sign == v.sign) {
  46.             bigint res = v;
  47.  
  48.             for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
  49.                 if (i == (int) res.a.size())
  50.                     res.a.push_back(0);
  51.                 res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
  52.                 carry = res.a[i] >= base;
  53.                 if (carry)
  54.                     res.a[i] -= base;
  55.             }
  56.             return res;
  57.         }
  58.         return *this - (-v);
  59.     }
  60.  
  61.     bigint operator-(const bigint &v) const {
  62.         if (sign == v.sign) {
  63.             if (abs() >= v.abs()) {
  64.                 bigint res = *this;
  65.                 for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
  66.                     res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
  67.                     carry = res.a[i] < 0;
  68.                     if (carry)
  69.                         res.a[i] += base;
  70.                 }
  71.                 res.trim();
  72.                 return res;
  73.             }
  74.             return -(v - *this);
  75.         }
  76.         return *this + (-v);
  77.     }
  78.  
  79.     void operator*=(int v) {
  80.         if (v < 0)
  81.             sign = -sign, v = -v;
  82.         for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
  83.             if (i == (int) a.size())
  84.                 a.push_back(0);
  85.             long long cur = a[i] * (long long) v + carry;
  86.             carry = (int) (cur / base);
  87.             a[i] = (int) (cur % base);
  88.             //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
  89.         }
  90.         trim();
  91.     }
  92.  
  93.     bigint operator*(int v) const {
  94.         bigint res = *this;
  95.         res *= v;
  96.         return res;
  97.     }
  98.  
  99.     friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
  100.         int norm = base / (b1.a.back() + 1);
  101.         bigint a = a1.abs() * norm;
  102.         bigint b = b1.abs() * norm;
  103.         bigint q, r;
  104.         q.a.resize(a.a.size());
  105.  
  106.         for (int i = a.a.size() - 1; i >= 0; i--) {
  107.             r *= base;
  108.             r += a.a[i];
  109.             int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
  110.             int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
  111.             int d = ((long long) base * s1 + s2) / b.a.back();
  112.             r -= b * d;
  113.             while (r < 0)
  114.                 r += b, --d;
  115.             q.a[i] = d;
  116.         }
  117.  
  118.         q.sign = a1.sign * b1.sign;
  119.         r.sign = a1.sign;
  120.         q.trim();
  121.         r.trim();
  122.         return make_pair(q, r / norm);
  123.     }
  124.  
  125.     bigint operator/(const bigint &v) const {
  126.         return divmod(*this, v).first;
  127.     }
  128.  
  129.     bigint operator%(const bigint &v) const {
  130.         return divmod(*this, v).second;
  131.     }
  132.  
  133.     void operator/=(int v) {
  134.         if (v < 0)
  135.             sign = -sign, v = -v;
  136.         for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
  137.             long long cur = a[i] + rem * (long long) base;
  138.             a[i] = (int) (cur / v);
  139.             rem = (int) (cur % v);
  140.         }
  141.         trim();
  142.     }
  143.  
  144.     bigint operator/(int v) const {
  145.         bigint res = *this;
  146.         res /= v;
  147.         return res;
  148.     }
  149.  
  150.     int operator%(int v) const {
  151.         if (v < 0)
  152.             v = -v;
  153.         int m = 0;
  154.         for (int i = a.size() - 1; i >= 0; --i)
  155.             m = (a[i] + m * (long long) base) % v;
  156.         return m * sign;
  157.     }
  158.  
  159.     void operator+=(const bigint &v) {
  160.         *this = *this + v;
  161.     }
  162.     void operator-=(const bigint &v) {
  163.         *this = *this - v;
  164.     }
  165.     void operator*=(const bigint &v) {
  166.         *this = *this * v;
  167.     }
  168.     void operator/=(const bigint &v) {
  169.         *this = *this / v;
  170.     }
  171.  
  172.     bool operator<(const bigint &v) const {
  173.         if (sign != v.sign)
  174.             return sign < v.sign;
  175.         if (a.size() != v.a.size())
  176.             return a.size() * sign < v.a.size() * v.sign;
  177.         for (int i = a.size() - 1; i >= 0; i--)
  178.             if (a[i] != v.a[i])
  179.                 return a[i] * sign < v.a[i] * sign;
  180.         return false;
  181.     }
  182.  
  183.     bool operator>(const bigint &v) const {
  184.         return v < *this;
  185.     }
  186.     bool operator<=(const bigint &v) const {
  187.         return !(v < *this);
  188.     }
  189.     bool operator>=(const bigint &v) const {
  190.         return !(*this < v);
  191.     }
  192.     bool operator==(const bigint &v) const {
  193.         return !(*this < v) && !(v < *this);
  194.     }
  195.     bool operator!=(const bigint &v) const {
  196.         return *this < v || v < *this;
  197.     }
  198.  
  199.     void trim() {
  200.         while (!a.empty() && !a.back())
  201.             a.pop_back();
  202.         if (a.empty())
  203.             sign = 1;
  204.     }
  205.  
  206.     bool isZero() const {
  207.         return a.empty() || (a.size() == 1 && !a[0]);
  208.     }
  209.  
  210.     bigint operator-() const {
  211.         bigint res = *this;
  212.         res.sign = -sign;
  213.         return res;
  214.     }
  215.  
  216.     bigint abs() const {
  217.         bigint res = *this;
  218.         res.sign *= res.sign;
  219.         return res;
  220.     }
  221.  
  222.     long long longValue() const {
  223.         long long res = 0;
  224.         for (int i = a.size() - 1; i >= 0; i--)
  225.             res = res * base + a[i];
  226.         return res * sign;
  227.     }
  228.  
  229.     friend bigint gcd(const bigint &a, const bigint &b) {
  230.         return b.isZero() ? a : gcd(b, a % b);
  231.     }
  232.     friend bigint lcm(const bigint &a, const bigint &b) {
  233.         return a / gcd(a, b) * b;
  234.     }
  235.  
  236.     void read(const string &s) {
  237.         sign = 1;
  238.         a.clear();
  239.         int pos = 0;
  240.         while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
  241.             if (s[pos] == '-')
  242.                 sign = -sign;
  243.             ++pos;
  244.         }
  245.         for (int i = s.size() - 1; i >= pos; i -= base_digits) {
  246.             int x = 0;
  247.             for (int j = max(pos, i - base_digits + 1); j <= i; j++)
  248.                 x = x * 10 + s[j] - '0';
  249.             a.push_back(x);
  250.         }
  251.         trim();
  252.     }
  253.  
  254.     friend istream& operator>>(istream &stream, bigint &v) {
  255.         string s;
  256.         stream >> s;
  257.         v.read(s);
  258.         return stream;
  259.     }
  260.  
  261.     friend ostream& operator<<(ostream &stream, const bigint &v) {
  262.         if (v.sign == -1)
  263.             stream << '-';
  264.         stream << (v.a.empty() ? 0 : v.a.back());
  265.         for (int i = (int) v.a.size() - 2; i >= 0; --i)
  266.             stream << setw(base_digits) << setfill('0') << v.a[i];
  267.         return stream;
  268.     }
  269.  
  270.     static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
  271.         vector<long long> p(max(old_digits, new_digits) + 1);
  272.         p[0] = 1;
  273.         for (int i = 1; i < (int) p.size(); i++)
  274.             p[i] = p[i - 1] * 10;
  275.         vector<int> res;
  276.         long long cur = 0;
  277.         int cur_digits = 0;
  278.         for (int i = 0; i < (int) a.size(); i++) {
  279.             cur += a[i] * p[cur_digits];
  280.             cur_digits += old_digits;
  281.             while (cur_digits >= new_digits) {
  282.                 res.push_back(int(cur % p[new_digits]));
  283.                 cur /= p[new_digits];
  284.                 cur_digits -= new_digits;
  285.             }
  286.         }
  287.         res.push_back((int) cur);
  288.         while (!res.empty() && !res.back())
  289.             res.pop_back();
  290.         return res;
  291.     }
  292.  
  293.     typedef vector<long long> vll;
  294.  
  295.     static vll karatsubaMultiply(const vll &a, const vll &b) {
  296.         int n = a.size();
  297.         vll res(n + n);
  298.         if (n <= 32) {
  299.             for (int i = 0; i < n; i++)
  300.                 for (int j = 0; j < n; j++)
  301.                     res[i + j] += a[i] * b[j];
  302.             return res;
  303.         }
  304.  
  305.         int k = n >> 1;
  306.         vll a1(a.begin(), a.begin() + k);
  307.         vll a2(a.begin() + k, a.end());
  308.         vll b1(b.begin(), b.begin() + k);
  309.         vll b2(b.begin() + k, b.end());
  310.  
  311.         vll a1b1 = karatsubaMultiply(a1, b1);
  312.         vll a2b2 = karatsubaMultiply(a2, b2);
  313.  
  314.         for (int i = 0; i < k; i++)
  315.             a2[i] += a1[i];
  316.         for (int i = 0; i < k; i++)
  317.             b2[i] += b1[i];
  318.  
  319.         vll r = karatsubaMultiply(a2, b2);
  320.         for (int i = 0; i < (int) a1b1.size(); i++)
  321.             r[i] -= a1b1[i];
  322.         for (int i = 0; i < (int) a2b2.size(); i++)
  323.             r[i] -= a2b2[i];
  324.  
  325.         for (int i = 0; i < (int) r.size(); i++)
  326.             res[i + k] += r[i];
  327.         for (int i = 0; i < (int) a1b1.size(); i++)
  328.             res[i] += a1b1[i];
  329.         for (int i = 0; i < (int) a2b2.size(); i++)
  330.             res[i + n] += a2b2[i];
  331.         return res;
  332.     }
  333.  
  334.     bigint operator*(const bigint &v) const {
  335.         vector<int> a6 = convert_base(this->a, base_digits, 6);
  336.         vector<int> b6 = convert_base(v.a, base_digits, 6);
  337.         vll a(a6.begin(), a6.end());
  338.         vll b(b6.begin(), b6.end());
  339.         while (a.size() < b.size())
  340.             a.push_back(0);
  341.         while (b.size() < a.size())
  342.             b.push_back(0);
  343.         while (a.size() & (a.size() - 1))
  344.             a.push_back(0), b.push_back(0);
  345.         vll c = karatsubaMultiply(a, b);
  346.         bigint res;
  347.         res.sign = sign * v.sign;
  348.         for (int i = 0, carry = 0; i < (int) c.size(); i++) {
  349.             long long cur = c[i] + carry;
  350.             res.a.push_back((int) (cur % 1000000));
  351.             carry = (int) (cur / 1000000);
  352.         }
  353.         res.a = convert_base(res.a, 6, base_digits);
  354.         res.trim();
  355.         return res;
  356.     }
  357. };
  358. //const int MOD = 9+98244353;
  359. const int MAXN = 5e2+7;
  360. const int maxn = 3e6;
  361. vector<ll> topo;
  362. static ll in[1000];
  363. ll dx[8] = {-1,0,0,1,-1,-1,1,1};
  364. ll dy[8] = {0,-1,1,0,-1,1,-1,1};
  365. static ll Hash,k,a[MAXN],p[MAXN],f[MAXN],b[MAXN],dp[MAXN],m,cnt,o1,o2,o3,o4;
  366. //mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  367. void qry(int limit,int be,int s,vector<int> &c){
  368.     if (limit==s){
  369.         for (int i = 1;i <= 50;i++)
  370.         p[i] = 0;
  371.         ll res = 0x3f3f3f;
  372.         for (int i = 0;i < c.size();i++)
  373.         p[c[i]]++;
  374.         for (int i = 0;i < c.size();i++)
  375.         res = min(res,f[c[i]]/p[c[i]]*p[c[i]]);
  376.         if (res==0)return ;
  377.         c.push_back(0);
  378.         for (int i = 0;i < c.size()-1;i++)
  379.         if (c[i]!=c[i+1])f[c[i]]-=res;
  380.         c.pop_back();
  381.         return ;
  382.     }
  383.     for (int i = min(limit-s,be);i >= 1;i--){
  384.         c.push_back(i);
  385.         qry(limit,i,s+i,c);
  386.         c.pop_back();
  387.     }
  388. }
  389. int main()
  390. {
  391.     ios_base::sync_with_stdio(false);
  392.     cin.tie(0); cout.tie(0);
  393.     //freopen("ROBOT.INP","r",stdin);
  394.     //freopen("ROBOT.OUT","w",stdout);
  395.     static ll tt,x,ans,y,xx,z,yy,j,l,r,lo,rr,i,n,res,index,note;
  396.     string ss,stt,sss,str,st;
  397.     while(cin >> n){
  398.         if (n==0)break;
  399.         for (i = 0;i <= 51;i++)
  400.         b[i] = f[i] = 0;
  401.         for (i = 1;i <= n;i++){
  402.             cin >> a[i];
  403.             b[a[i]]++;
  404.         }
  405.         for (i = 1;i <= 50;i++)
  406.         {
  407.             vector<int> c;
  408.             for (j = 1;j <= 50;j++)
  409.             f[j] = b[j];
  410.             qry(i,i,0,c);
  411.             bool ok = true;
  412.             for (j = 1;j <= 50;j++)
  413.             if (f[j]>0)ok = false;
  414.             if (ok){
  415.                 cout << i << '\n';
  416.                 break;
  417.             }
  418.         }
  419.     }
  420.     return (0^0)&(200+10);
  421. }
  422.  
  423. /*
  424. 3
  425. 2 5 3
  426.  
  427. ඞඞඞඞඞ
  428. 3 3
  429. 3 4 5
  430. 2 3 4
  431. 5 4 3
  432. e.g
  433. build
  434. dp[2][1][1]
  435. min(dp[1][1][1],dp[1][1][2],dp[1][2][1],dp[1][2][2]);
  436. 1 1 1 1
  437. 1 1 1 1
  438. 1 1 1 1
  439. 1 1 1 1
  440. */
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/l0jgBB
language:
C++14 (gcc 8.3)
created:
13 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!