oj.uz

Submission #394467

# Submission time Handle Problem Language Result Execution time Memory
394467 2021-04-26T17:18:34 Z MarcoMeijer Parrots (IOI11_parrots) C++14
100 / 100
 283 ms 61452 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()

const int MX = 80;

struct BigNumb {
    int v[MX];
    BigNumb() {
        RE(i,MX) v[i] = 0;
    }
    BigNumb(int x) {
        RE(i,MX) v[i] = 0;
        v[0] = x;
        update();
    }
    BigNumb operator+(const BigNumb& rhs) const {
        BigNumb result;
        result = *this;
        RE(i,MX) result.v[i] += rhs.v[i];
        result.update();
        return result;
    }
    BigNumb operator-(const BigNumb& rhs) const {
        BigNumb result;
        result = *this;
        REV(i,1,MX) {
            result.v[i] -= rhs.v[i];
            if(result.v[i]) {
                result.v[i]--;
                result.v[i-1] += 256;
            }
        }
        result.v[0] -= rhs.v[0];
        result.update();
        return result;
    }
    BigNumb& operator+=(const BigNumb& rhs) {*this = (*this)+rhs; return *this;}
    BigNumb& operator-=(const BigNumb& rhs) {*this = (*this)-rhs; return *this;}
    BigNumb& operator=(int rhs) {*this = BigNumb(rhs); return *this;}
    bool operator>=(const BigNumb& rhs) const {
        REV(i,0,MX) if(v[i] != rhs.v[i]) return v[i] > rhs.v[i];
        return true;
    }
    void update() {
        RE(i,MX-1) while(v[i] >= 256) v[i] -= 256, v[i+1]++;
    }
};

BigNumb ways[350][270];

void fillWays() {
    RE(i,270) ways[0][i] = i+1;
    REP(i,1,350) RE(j,270) {
        if(j) ways[i][j] += ways[i][j-1];
        ways[i][j] += ways[i-1][j];
    }
}
BigNumb getWays(int dif, int len) {
    if(dif == 0) return BigNumb(0);
    return ways[len-1][dif-1];
}
vll encode(BigNumb x, int mx, int len) {
    if(len == 0) return {};
    RE1(i,mx) {
        if(getWays(i,len) >= x) {
            vll res = encode(x - getWays(i-1,len), i, len-1);
            res.pb(i);
            return res;
        }
    }
    return {};
}

void encode(int N, int M[]) {
    static bool first = true;
    if(first) {
        fillWays();
        first = false;
    }

    BigNumb x;
    RE(i,N) x.v[i] = M[i];
    x += BigNumb(1);
    vll res = encode(x, 256, N*5);
    FOR(i,res) send(i-1);
}

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()

const int MX = 80;

struct BigNumb {
    int v[MX];
    BigNumb() {
        RE(i,MX) v[i] = 0;
    }
    BigNumb(int x) {
        RE(i,MX) v[i] = 0;
        v[0] = x;
        update();
    }
    BigNumb operator+(const BigNumb& rhs) const {
        BigNumb result;
        result = *this;
        RE(i,MX) result.v[i] += rhs.v[i];
        result.update();
        return result;
    }
    BigNumb operator-(const BigNumb& rhs) const {
        BigNumb result;
        result = *this;
        REV(i,1,MX) {
            result.v[i] -= rhs.v[i];
            if(result.v[i]) {
                result.v[i]--;
                result.v[i-1] += 256;
            }
        }
        result.v[0] -= rhs.v[0];
        result.update();
        return result;
    }
    BigNumb& operator+=(const BigNumb& rhs) {*this = (*this)+rhs; return *this;}
    BigNumb& operator-=(const BigNumb& rhs) {*this = (*this)-rhs; return *this;}
    BigNumb& operator=(int rhs) {*this = BigNumb(rhs); return *this;}
    bool operator>=(const BigNumb& rhs) const {
        REV(i,0,MX) if(v[i] != rhs.v[i]) return v[i] > rhs.v[i];
        return true;
    }
    void update() {
        RE(i,MX-1) while(v[i] >= 256) v[i] -= 256, v[i+1]++;
    }
};

BigNumb ways[350][270];

void fillWays() {
    RE(i,270) ways[0][i] = i+1;
    REP(i,1,350) RE(j,270) {
        if(j) ways[i][j] += ways[i][j-1];
        ways[i][j] += ways[i-1][j];
    }
}
BigNumb getWays(int dif, int len) {
    if(dif == 0) return BigNumb(0);
    return ways[len-1][dif-1];
}
vll encode(BigNumb x, int mx, int len) {
    if(len == 0) return {};
    RE1(i,mx) {
        if(getWays(i,len) >= x) {
            vll res = encode(x - getWays(i-1,len), i, len-1);
            res.pb(i);
            return res;
        }
    }
    return {};
}
BigNumb decode(vll v) {
    if(v.empty()) return 1;
    int last = v.back();
    v.pop_back();
    BigNumb res = decode(v);
    res += getWays(last-1, v.size()+1);
    return res;
}

void decode(int N, int L, int X[]) {
    static bool first = true;
    if(first) {
        fillWays();
        first = false;
    }
    
    vll v;
    RE(i,L) v.pb(X[i]+1);
    sort(all(v));
    BigNumb res = decode(v);
    res -= BigNumb(1);
    RE(i,N) output(res.v[i]);
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 59864 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 60240 KB Output is correct
2 Correct 159 ms 60248 KB Output is correct
3 Correct 166 ms 60196 KB Output is correct
4 Correct 166 ms 60360 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 60156 KB Output is correct
2 Correct 164 ms 60204 KB Output is correct
3 Correct 165 ms 60496 KB Output is correct
4 Correct 164 ms 60220 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 60152 KB Output is correct
2 Correct 164 ms 60352 KB Output is correct
3 Correct 170 ms 60456 KB Output is correct
4 Correct 195 ms 60464 KB Output is correct
5 Correct 195 ms 60728 KB Output is correct
6 Correct 195 ms 60600 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 60284 KB Output is correct - P = 5.000000
2 Correct 198 ms 60620 KB Output is correct - P = 5.000000
3 Correct 197 ms 60584 KB Output is correct - P = 5.000000
4 Correct 243 ms 60992 KB Output is correct - P = 5.000000
5 Correct 272 ms 61300 KB Output is correct - P = 5.000000
6 Correct 282 ms 61452 KB Output is correct - P = 5.000000
7 Correct 283 ms 61304 KB Output is correct - P = 5.000000