Submission #712359

#	Time	Username	Problem	Language	Result	Execution time	Memory
712359		BackNoob	Parrots (IOI11_parrots)	C++14	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

string getstring(int x)
{
    string res = "";
    while(x) {
        res += char('0' + x % 10);
        x /= 10;
    }
    reverse(all(res));
    return res;
}

int getval(string tmp)
{
    int res = 0;
    for(auto it : tmp) res = res * 10 + it - '0';
    return res;
}

string add(string &a, string &b)
{
    string res = "";
    int i = sz(a) - 1;
    int j = sz(b) - 1;
    int carry = 0;
    while(i >= 0 || j >= 0) {
        int x, y;
        if(i >= 0) x = a[i] - '0';
        else x = 0;
        if(j >= 0) y = b[j] - '0';
        else y = 0;

        int tmp = (x + y + carry) % 10;
        carry = (x + y + carry) / 10;
        res += char('0' + tmp);
        --i;
        --j;
    }

    if(carry) res += char('1');
    reverse(all(res));
    return res;
}

string sub(string &a, string &b)
{
    string res = "";
    int i = sz(a) - 1;
    int j = sz(b) - 1;
    int carry = 0;
    while(i >= 0 || j >= 0) {
        int x, y;
        if(i >= 0) x = a[i] - '0';
        else x = 0;
        if(j >= 0) y = b[j] - '0';
        else y = 0;

        x -= carry;
        if(x < y) {
            x += 10;
            carry = 1;
        }
        else carry = 0;
        res += char('0' + (x - y));
        --i;
        --j;
    }

    while(res.back() == '0') res.pop_back();
    if(sz(res) == 0) res = "0";

    reverse(all(res));
    return res;
}

int cmp(string &a, string &b)
{
    if(sz(a) == sz(b)) {
        for(int i = 0; i < sz(a); i++) {
            if(a[i] == b[i]) continue;
            if(a[i] < b[i]) return -1;
            return 1;
        }

        return 0;
    }
    if(sz(a) < sz(b)) return -1;
    return 1;

}

void encode(int n, int a[])
{
    string x = "";
    for(int i = 0; i < n; i++) {
        string tmp = getstring(a[i]);
        if(i) {
            while(sz(tmp) < 3) tmp = '0' + tmp;
        }
        x += tmp;
    }

    vector<vector<string>> choose;
    choose.resize(507, vector<string>(300));

    for(int i = 0; i <= 500; i++) {
        choose[i][0] = "1";
        for(int j = 1; j <= min(256, i); j++) {
            choose[i][j] = add(choose[i - 1][j], choose[i - 1][j - 1]);
        }
    }

    int k = 1;
    while(cmp(choose[256 + k][256], x) == -1) ++k;

    int sta = 0;
    for(int i = 1; i <= k; i++) {
        for(int j = sta; j <= 255; j++) {
            string way = choose[256 - j + (k - i)][256 - j];
            int tmp = cmp(x, way);
            if(tmp <= 0) {
                send(j);
                sta = j;
                break;
            }
            else {
                x = sub(x, way);
            }
        }
    }
}

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

string getstring(int x)
{
    string res = "";
    while(x) {
        res += char('0' + x % 10);
        x /= 10;
    }
    reverse(all(res));
    return res;
}

int getval(string tmp)
{
    int res = 0;
    for(auto it : tmp) res = res * 10 + it - '0';
    return res;
}

string add(string &a, string &b)
{
    string res = "";
    int i = sz(a) - 1;
    int j = sz(b) - 1;
    int carry = 0;
    while(i >= 0 || j >= 0) {
        int x, y;
        if(i >= 0) x = a[i] - '0';
        else x = 0;
        if(j >= 0) y = b[j] - '0';
        else y = 0;

        int tmp = (x + y + carry) % 10;
        carry = (x + y + carry) / 10;
        res += char('0' + tmp);
        --i;
        --j;
    }

    if(carry) res += char('1');
    reverse(all(res));
    return res;
}

string sub(string &a, string &b)
{
    string res = "";
    int i = sz(a) - 1;
    int j = sz(b) - 1;
    int carry = 0;
    while(i >= 0 || j >= 0) {
        int x, y;
        if(i >= 0) x = a[i] - '0';
        else x = 0;
        if(j >= 0) y = b[j] - '0';
        else y = 0;

        x -= carry;
        if(x < y) {
            x += 10;
            carry = 1;
        }
        else carry = 0;
        res += char('0' + (x - y));
        --i;
        --j;
    }

    while(res.back() == '0') res.pop_back();
    if(sz(res) == 0) res = "0";

    reverse(all(res));
    return res;
}

int cmp(string &a, string &b)
{
    if(sz(a) == sz(b)) {
        for(int i = 0; i < sz(a); i++) {
            if(a[i] == b[i]) continue;
            if(a[i] < b[i]) return -1;
            return 1;
        }

        return 0;
    }
    if(sz(a) < sz(b)) return -1;
    return 1;

}

void decode(int n, int l, int a[])
{   
    vector<int> v;
    for(int i = 0; i < l; i++) v.pb(a[i]);
    sort(all(v));
    
    vector<vector<string>> choose;
    choose.resize(507, vector<string>(300));

    for(int i = 0; i <= 500; i++) {
        choose[i][0] = "1";
        for(int j = 1; j <= min(256, i); j++) {
            choose[i][j] = add(choose[i - 1][j], choose[i - 1][j - 1]);
        }
    }

    string res = "1";

    int sta = 0;
    for(int i = 1; i <= sz(v); i++) {
        int x = v[i - 1];
        for(int j = sta; j < x; j++) {
            res = add(res, choose[(256 - j) + (sz(v) - i)][(256 - j)]);
        }
        sta = x;
    }

    vector<int> ans;
    for(int i = 0; i < n; i++) {
        string tmp = "";
        if(i) {
            for(int j = 0; j < 3; j++) {
                tmp += res.back();
                res.pop_back();
            }
            reverse(all(tmp));
            ans.pb(getval(tmp));
        }
    }
    ans.pb(getval(res));
    reverse(all(ans));
    for(auto it : ans) output(it);
}

Compilation message (stderr)

encoder.cpp:17:1: error: 'string' does not name a type; did you mean 'stdin'?
   17 | string getstring(int x)
      | ^~~~~~
      | stdin
encoder.cpp:28:12: error: 'string' was not declared in this scope; did you mean 'std::string'?
   28 | int getval(string tmp)
      |            ^~~~~~
      |            std::string
In file included from /usr/include/c++/10/iosfwd:39,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from encoder.cpp:3:
/usr/include/c++/10/bits/stringfwd.h:79:33: note: 'std::string' declared here
   79 |   typedef basic_string<char>    string;
      |                                 ^~~~~~
encoder.cpp:35:1: error: 'string' does not name a type; did you mean 'stdin'?
   35 | string add(string &a, string &b)
      | ^~~~~~
      | stdin
encoder.cpp:60:1: error: 'string' does not name a type; did you mean 'stdin'?
   60 | string sub(string &a, string &b)
      | ^~~~~~
      | stdin
encoder.cpp:91:9: error: 'string' was not declared in this scope; did you mean 'std::string'?
   91 | int cmp(string &a, string &b)
      |         ^~~~~~
      |         std::string
In file included from /usr/include/c++/10/iosfwd:39,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from encoder.cpp:3:
/usr/include/c++/10/bits/stringfwd.h:79:33: note: 'std::string' declared here
   79 |   typedef basic_string<char>    string;
      |                                 ^~~~~~
encoder.cpp:91:17: error: 'a' was not declared in this scope
   91 | int cmp(string &a, string &b)
      |                 ^
encoder.cpp:91:20: error: 'string' was not declared in this scope; did you mean 'std::string'?
   91 | int cmp(string &a, string &b)
      |                    ^~~~~~
      |                    std::string
In file included from /usr/include/c++/10/iosfwd:39,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from encoder.cpp:3:
/usr/include/c++/10/bits/stringfwd.h:79:33: note: 'std::string' declared here
   79 |   typedef basic_string<char>    string;
      |                                 ^~~~~~
encoder.cpp:91:28: error: 'b' was not declared in this scope; did you mean 'pb'?
   91 | int cmp(string &a, string &b)
      |                            ^
      |                            pb
encoder.cpp:91:29: error: expression list treated as compound expression in initializer [-fpermissive]
   91 | int cmp(string &a, string &b)
      |                             ^
encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:109:5: error: 'string' was not declared in this scope; did you mean 'std::string'?
  109 |     string x = "";
      |     ^~~~~~
      |     std::string
In file included from /usr/include/c++/10/iosfwd:39,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from encoder.cpp:3:
/usr/include/c++/10/bits/stringfwd.h:79:33: note: 'std::string' declared here
   79 |   typedef basic_string<char>    string;
      |                                 ^~~~~~
encoder.cpp:111:15: error: expected ';' before 'tmp'
  111 |         string tmp = getstring(a[i]);
      |               ^~~~
      |               ;
encoder.cpp:113:22: error: 'tmp' was not declared in this scope; did you mean 'cmp'?
  113 |             while(sz(tmp) < 3) tmp = '0' + tmp;
      |                      ^~~
encoder.cpp:15:22: note: in definition of macro 'sz'
   15 | #define sz(s) (int) (s).size()
      |                      ^
encoder.cpp:115:9: error: 'x' was not declared in this scope
  115 |         x += tmp;
      |         ^
encoder.cpp:115:14: error: 'tmp' was not declared in this scope; did you mean 'cmp'?
  115 |         x += tmp;
      |              ^~~
      |              cmp
encoder.cpp:118:5: error: 'vector' was not declared in this scope; did you mean 'std::vector'?
  118 |     vector<vector<string>> choose;
      |     ^~~~~~
      |     std::vector
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from encoder.cpp:3:
/usr/include/c++/10/bits/stl_vector.h:389:11: note: 'std::vector' declared here
  389 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
encoder.cpp:118:28: error: 'choose' was not declared in this scope
  118 |     vector<vector<string>> choose;
      |                            ^~~~~~
encoder.cpp:123:29: error: 'min' was not declared in this scope; did you mean 'std::min'?
  123 |         for(int j = 1; j <= min(256, i); j++) {
      |                             ^~~
      |                             std::min
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from encoder.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: 'std::min' declared here
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
encoder.cpp:124:28: error: 'add' was not declared in this scope; did you mean 'fadd'?
  124 |             choose[i][j] = add(choose[i - 1][j], choose[i - 1][j - 1]);
      |                            ^~~
      |                            fadd
encoder.cpp:129:37: error: 'x' was not declared in this scope
  129 |     while(cmp(choose[256 + k][256], x) == -1) ++k;
      |                                     ^
encoder.cpp:129:38: error: 'cmp' cannot be used as a function
  129 |     while(cmp(choose[256 + k][256], x) == -1) ++k;
      |                                      ^
encoder.cpp:134:19: error: expected ';' before 'way'
  134 |             string way = choose[256 - j + (k - i)][256 - j];
      |                   ^~~~
      |                   ;
encoder.cpp:135:27: error: 'x' was not declared in this scope
  135 |             int tmp = cmp(x, way);
      |                           ^
encoder.cpp:135:30: error: 'way' was not declared in this scope
  135 |             int tmp = cmp(x, way);
      |                              ^~~
encoder.cpp:135:33: error: 'cmp' cannot be used as a function
  135 |             int tmp = cmp(x, way);
      |                                 ^
encoder.cpp:142:21: error: 'sub' was not declared in this scope; did you mean 'fsub'?
  142 |                 x = sub(x, way);
      |                     ^~~
      |                     fsub

decoder.cpp:17:1: error: 'string' does not name a type; did you mean 'stdin'?
   17 | string getstring(int x)
      | ^~~~~~
      | stdin
decoder.cpp:28:12: error: 'string' was not declared in this scope; did you mean 'std::string'?
   28 | int getval(string tmp)
      |            ^~~~~~
      |            std::string
In file included from /usr/include/c++/10/iosfwd:39,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from decoder.cpp:3:
/usr/include/c++/10/bits/stringfwd.h:79:33: note: 'std::string' declared here
   79 |   typedef basic_string<char>    string;
      |                                 ^~~~~~
decoder.cpp:35:1: error: 'string' does not name a type; did you mean 'stdin'?
   35 | string add(string &a, string &b)
      | ^~~~~~
      | stdin
decoder.cpp:60:1: error: 'string' does not name a type; did you mean 'stdin'?
   60 | string sub(string &a, string &b)
      | ^~~~~~
      | stdin
decoder.cpp:91:9: error: 'string' was not declared in this scope; did you mean 'std::string'?
   91 | int cmp(string &a, string &b)
      |         ^~~~~~
      |         std::string
In file included from /usr/include/c++/10/iosfwd:39,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from decoder.cpp:3:
/usr/include/c++/10/bits/stringfwd.h:79:33: note: 'std::string' declared here
   79 |   typedef basic_string<char>    string;
      |                                 ^~~~~~
decoder.cpp:91:17: error: 'a' was not declared in this scope
   91 | int cmp(string &a, string &b)
      |                 ^
decoder.cpp:91:20: error: 'string' was not declared in this scope; did you mean 'std::string'?
   91 | int cmp(string &a, string &b)
      |                    ^~~~~~
      |                    std::string
In file included from /usr/include/c++/10/iosfwd:39,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from decoder.cpp:3:
/usr/include/c++/10/bits/stringfwd.h:79:33: note: 'std::string' declared here
   79 |   typedef basic_string<char>    string;
      |                                 ^~~~~~
decoder.cpp:91:28: error: 'b' was not declared in this scope; did you mean 'pb'?
   91 | int cmp(string &a, string &b)
      |                            ^
      |                            pb
decoder.cpp:91:29: error: expression list treated as compound expression in initializer [-fpermissive]
   91 | int cmp(string &a, string &b)
      |                             ^
decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:109:5: error: 'vector' was not declared in this scope; did you mean 'std::vector'?
  109 |     vector<int> v;
      |     ^~~~~~
      |     std::vector
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from decoder.cpp:3:
/usr/include/c++/10/bits/stl_vector.h:389:11: note: 'std::vector' declared here
  389 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
decoder.cpp:109:12: error: expected primary-expression before 'int'
  109 |     vector<int> v;
      |            ^~~
decoder.cpp:110:32: error: 'v' was not declared in this scope
  110 |     for(int i = 0; i < l; i++) v.pb(a[i]);
      |                                ^
decoder.cpp:111:14: error: 'v' was not declared in this scope
  111 |     sort(all(v));
      |              ^
decoder.cpp:12:17: note: in definition of macro 'all'
   12 | #define all(x) (x).begin() , (x).end()
      |                 ^
decoder.cpp:111:5: error: 'sort' was not declared in this scope; did you mean 'std::sort'?
  111 |     sort(all(v));
      |     ^~~~
      |     std::sort
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from decoder.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:4880:5: note: 'std::sort' declared here
 4880 |     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
      |     ^~~~
decoder.cpp:113:19: error: 'string' was not declared in this scope; did you mean 'std::string'?
  113 |     vector<vector<string>> choose;
      |                   ^~~~~~
      |                   std::string
In file included from /usr/include/c++/10/iosfwd:39,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from decoder.cpp:3:
/usr/include/c++/10/bits/stringfwd.h:79:33: note: 'std::string' declared here
   79 |   typedef basic_string<char>    string;
      |                                 ^~~~~~
decoder.cpp:113:28: error: 'choose' was not declared in this scope
  113 |     vector<vector<string>> choose;
      |                            ^~~~~~
decoder.cpp:118:29: error: 'min' was not declared in this scope; did you mean 'std::min'?
  118 |         for(int j = 1; j <= min(256, i); j++) {
      |                             ^~~
      |                             std::min
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from decoder.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: 'std::min' declared here
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
decoder.cpp:119:28: error: 'add' was not declared in this scope; did you mean 'fadd'?
  119 |             choose[i][j] = add(choose[i - 1][j], choose[i - 1][j - 1]);
      |                            ^~~
      |                            fadd
decoder.cpp:123:11: error: expected ';' before 'res'
  123 |     string res = "1";
      |           ^~~~
      |           ;
decoder.cpp:129:13: error: 'res' was not declared in this scope
  129 |             res = add(res, choose[(256 - j) + (sz(v) - i)][(256 - j)]);
      |             ^~~
decoder.cpp:129:19: error: 'add' was not declared in this scope; did you mean 'fadd'?
  129 |             res = add(res, choose[(256 - j) + (sz(v) - i)][(256 - j)]);
      |                   ^~~
      |                   fadd
decoder.cpp:134:12: error: expected primary-expression before 'int'
  134 |     vector<int> ans;
      |            ^~~
decoder.cpp:136:15: error: expected ';' before 'tmp'
  136 |         string tmp = "";
      |               ^~~~
      |               ;
decoder.cpp:139:17: error: 'tmp' was not declared in this scope; did you mean 'cmp'?
  139 |                 tmp += res.back();
      |                 ^~~
      |                 cmp
decoder.cpp:139:24: error: 'res' was not declared in this scope
  139 |                 tmp += res.back();
      |                        ^~~
decoder.cpp:142:25: error: 'tmp' was not declared in this scope; did you mean 'cmp'?
  142 |             reverse(all(tmp));
      |                         ^~~
decoder.cpp:12:17: note: in definition of macro 'all'
   12 | #define all(x) (x).begin() , (x).end()
      |                 ^
decoder.cpp:142:13: error: 'reverse' was not declared in this scope; did you mean 'std::reverse'?
  142 |             reverse(all(tmp));
      |             ^~~~~~~
      |             std::reverse
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from decoder.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:1165:5: note: 'std::reverse' declared here
 1165 |     reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
      |     ^~~~~~~
decoder.cpp:143:13: error: 'ans' was not declared in this scope; did you mean 'abs'?
  143 |             ans.pb(getval(tmp));
      |             ^~~
      |             abs
decoder.cpp:143:30: error: 'getval' cannot be used as a function
  143 |             ans.pb(getval(tmp));
      |                              ^
decoder.cpp:146:5: error: 'ans' was not declared in this scope; did you mean 'abs'?
  146 |     ans.pb(getval(res));
      |     ^~~
      |     abs
decoder.cpp:146:19: error: 'res' was not declared in this scope
  146 |     ans.pb(getval(res));
      |                   ^~~
decoder.cpp:146:22: error: 'getval' cannot be used as a function
  146 |     ans.pb(getval(res));
      |                      ^
decoder.cpp:147:5: error: 'reverse' was not declared in this scope; did you mean 'std::reverse'?
  147 |     reverse(all(ans));
      |     ^~~~~~~
      |     std::reverse
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from decoder.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:1165:5: note: 'std::reverse' declared here
 1165 |     reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
      |     ^~~~~~~