oj.uz

답안 #676780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
676780 2023-01-01T05:57:42 Z Alan 앵무새 (IOI11_parrots) C++17
0 / 100
 84 ms 65904 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct BigInt {
	static const ll unit = 1000000000, digit = 9;
	vector<ll> x {0};
	BigInt () {}
	BigInt (vector<ll> y) {
		x = y;
	}
	BigInt (ll y) {
		x.resize(3);
		x[0] = y%unit;
		x[1] = y/unit%unit;
		x[2] = y/unit/unit;
		while (x.back() == 0 && (int) x.size() > 1) x.pop_back();
	}
	BigInt operator+ (BigInt y) {
		BigInt tmp = BigInt(x);
		if (y.x.size() < tmp.x.size()) swap(y, tmp);
		for (int i = 0; i < (int) tmp.x.size(); i++) y.x[i] += tmp.x[i];
		y.x.push_back(0);
		for (int i = 0; i < (int) y.x.size()-1; i++) if (y.x[i] >= 1e9) {
			y.x[i+1] += y.x[i]/unit;
			y.x[i] %= unit;
		}
		if ((int) y.x.size() > 1 && y.x.back() == 0) y.x.pop_back();
		return y;
	}
	BigInt operator* (BigInt y) {
		BigInt tmp = BigInt(x), res (0);
		res.x.resize(y.x.size()+tmp.x.size()+1);
		for (int i = 0; i < (int) y.x.size(); i++) for (int j = 0; j < (int) tmp.x.size(); j++) res.x[i+j] += y.x[i]*tmp.x[j];
		for (int i = 0; i < (int) res.x.size()-1; i++) if (res.x[i] >= 1e9) {
			res.x[i+1] += res.x[i]/unit;
			res.x[i] %= unit;
		}
		while ((int) res.x.size() > 1 && res.x.back() == 0) res.x.pop_back();
		return res;
	}
	bool operator== (BigInt y) {
		if (x.size() != y.x.size()) return false;
		for (int i = 0; i < (int) x.size(); i++) if (x[i] != y.x[i]) return false;
		return true;
	}
	bool operator<= (BigInt y) {
		if (x.size() < y.x.size()) return true;
		if (x.size() > y.x.size()) return false;
		for (int i = (int) x.size()-1; i >= 0; i--) {
			if (x[i] < y.x[i]) return true;
			if (x[i] > y.x[i]) return false;
		}
		return true;
	}
};

BigInt pow (BigInt x, ll p) {
	if (!p) return BigInt(1);
	BigInt t = pow(x, p/2);
	t = t*t;
	return p % 2 == 1 ? t * x : t;
}

ostream& operator<< (ostream& o, BigInt x) {
	string s;
	for (int i = (int) x.x.size() - 1; i >= 0; i--) {
		if (i != (int) x.x.size() - 1) for (int j = 0; j < x.digit - (int) to_string(x.x[i]).size(); j++) s.push_back('0');
		s += to_string(x.x[i]);
	}
	return o << s;
}

BigInt ncr[600][350];

void precomp () {
	for (int i = 0; i < 600; i++) for (int j = 0; j <= min(i, 400); j++) {
		if (j == 0 || j == i) ncr[i][j] = BigInt(1);
		else ncr[i][j] = ncr[i-1][j]+ncr[i-1][j-1];
	}
}

void encode (int n, int m[]) {
	precomp();
	BigInt res (0), rep (0);
	for (int i = 0; i < n; i++) res = res + BigInt(m[i]) * pow(BigInt(256), i);
	int last = 0;
	for (int i = 0; i < n*5; i++) {
		if (i == n*5-1) {
			for (int j = 0; j < 256; j++) if (rep+BigInt(j) == res) {
				send(last+j);
				break;
			}
			break;
		}
		while (rep + ncr[254-last+n*5-i][n*5-i-1] <= res) {
			rep = rep + ncr[254-last+n*5-i][n*5-i-1];
			last++;
		}
		send(last);
	}
}
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct BigInt {
	static const ll unit = 1000000000, digit = 9;
	vector<ll> x {0};
	BigInt () {}
	BigInt (vector<ll> y) {
		x = y;
	}
	BigInt (ll y) {
		x.resize(3);
		x[0] = y%unit;
		x[1] = y/unit%unit;
		x[2] = y/unit/unit;
		while (x.back() == 0 && (int) x.size() > 1) x.pop_back();
	}
	BigInt operator+ (BigInt y) {
		BigInt tmp = BigInt(x);
		if (y.x.size() < tmp.x.size()) swap(y, tmp);
		for (int i = 0; i < (int) tmp.x.size(); i++) y.x[i] += tmp.x[i];
		y.x.push_back(0);
		for (int i = 0; i < (int) y.x.size()-1; i++) if (y.x[i] >= 1e9) {
			y.x[i+1] += y.x[i]/unit;
			y.x[i] %= unit;
		}
		if ((int) y.x.size() > 1 && y.x.back() == 0) y.x.pop_back();
		return y;
	}
	BigInt operator* (BigInt y) {
		BigInt tmp = BigInt(x), res (0);
		res.x.resize(y.x.size()+tmp.x.size()+1);
		for (int i = 0; i < (int) y.x.size(); i++) for (int j = 0; j < (int) tmp.x.size(); j++) res.x[i+j] += y.x[i]*tmp.x[j];
		for (int i = 0; i < (int) res.x.size()-1; i++) if (res.x[i] >= 1e9) {
			res.x[i+1] += res.x[i]/unit;
			res.x[i] %= unit;
		}
		while ((int) res.x.size() > 1 && res.x.back() == 0) res.x.pop_back();
		return res;
	}
	bool operator== (BigInt y) {
		if (x.size() != y.x.size()) return false;
		for (int i = 0; i < (int) x.size(); i++) if (x[i] != y.x[i]) return false;
		return true;
	}
	bool operator<= (BigInt y) {
		if (x.size() < y.x.size()) return true;
		if (x.size() > y.x.size()) return false;
		for (int i = (int) x.size()-1; i >= 0; i--) {
			if (x[i] < y.x[i]) return true;
			if (x[i] > y.x[i]) return false;
		}
		return true;
	}
};

BigInt pow (BigInt x, ll p) {
	if (!p) return BigInt(1);
	BigInt t = pow(x, p/2);
	t = t*t;
	return p % 2 == 1 ? t * x : t;
}

ostream& operator<< (ostream& o, BigInt x) {
	string s;
	for (int i = (int) x.x.size() - 1; i >= 0; i--) {
		if (i != (int) x.x.size() - 1) for (int j = 0; j < x.digit - (int) to_string(x.x[i]).size(); j++) s.push_back('0');
		s += to_string(x.x[i]);
	}
	return o << s;
}

BigInt ncr[600][350];

void precomp () {
	for (int i = 0; i < 600; i++) for (int j = 0; j <= min(i, 400); j++) {
		if (j == 0 || j == i) ncr[i][j] = BigInt(1);
		else ncr[i][j] = ncr[i-1][j]+ncr[i-1][j-1];
	}
}

void decode (int n, int l, int x[]) {
	BigInt res (0), rep (0);
	vector<int> ans (n);
	sort(x, x+l);
	for (int i = x[l-2]; i < x[l-1]; i++) res = res + 1;
	int last = 0;
	for (int i = 0; i < l-1; i++) for (; last < x[i]; last++) res = res + ncr[254-last+n*5-i][n*5-i-1];
	for (int i = n-1; i >= 0; i--) {
		while (rep + BigInt(ans[i]+1) * pow(BigInt(256), i) <= res) ans[i]++;
		rep = rep + BigInt(ans[i]) * pow(BigInt(256), i);
	}
	for (int i = 0; i < n; i++) output(ans[i]);
}

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 84 ms 65896 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 77 ms 65832 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 80 ms 65872 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 76 ms 65856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 77 ms 65792 KB Execution killed with signal 11
2 Runtime error 77 ms 65904 KB Execution killed with signal 11
3 Runtime error 78 ms 65836 KB Execution killed with signal 11
4 Runtime error 76 ms 65860 KB Execution killed with signal 11
5 Runtime error 81 ms 65852 KB Execution killed with signal 11
6 Runtime error 76 ms 65876 KB Execution killed with signal 11
7 Runtime error 80 ms 65804 KB Execution killed with signal 11