Submission #919978

#	Time	Username	Problem	Language	Result	Execution time	Memory
919978		Lobo	Parrots (IOI11_parrots)	C++17	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 "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fr first
#define sc second
#define int long long
// const int maxn = 1e5+10;
// const int inf = 1e18+10;
static vector<int> maxt1;
static int R1;
static int k1;
static int base1 = 1e9;

bool geq1(vector<int> s, vector<int> t) {
	if(s.size() > t.size()) return 1;
	if(t.size() > s.size()) return 0;

	for(int i = (int) s.size() -1; i >= 0; i--) {
		if(s[i] > t[i]) return 1;
		if(t[i] > s[i]) return 0;
	}
	return 1;
}

vector<int> mult1(vector<int> s, vector<int> t) {
	vector<int> ans((int) s.size()+(int) t.size(),0);
	if(s == vector<int>{0} or t == vector<int>{0}) return vector<int>{0};

	for(int i = 0; i < s.size(); i++) {
		for(int j = 0; j < t.size(); j++) {
			ans[i+j]+= s[i]*t[j];
		}
	}

	for(int i = 0; i < ans.size(); i++) {
		if(ans[i] >= base1) {
			if(i+1 == (int) ans.size()) ans.pb(0);
			ans[i+1]+= ans[i]/base1;
			ans[i]%= base1;
		}
	}
	while(ans.size() > 1 && ans.back() == 0) ans.pop_back();
	if(geq1(ans,maxt1)) return maxt1;
	return ans;
}

vector<int> neg(vector<int> s) {
	for(int i = 0; i < s.size(); i++) {
		s[i]*= -1;
	}
	return s;
}

vector<int> add1(vector<int> s, vector<int> t) {
	vector<int> ans = s;

	for(int i = 0; i < t.size(); i++) {
		if(i == (int) ans.size()) ans.pb(0);
		ans[i]+= t[i];
	}

	for(int i = 0; i < ans.size(); i++) {
		if(ans[i] >= base1) {
			if(i+1 == (int) ans.size()) ans.pb(0);
			ans[i+1]+= ans[i]/base1;
			ans[i]%= base1;
		}

		// if(ans[i] <= -10) {
		// 	if(i+1 == (int) ans.size()) ans.pb(0);
		// 	ans[i+1]+= ans[i]/10;
		// 	ans[i]%= 10;
		// }
	}

	for(int i = 0; i+1 < ans.size(); i++) {
		while(ans[i] < 0) {
			ans[i]+= base1;
			ans[i+1]-= 1;
		}
	}
	for(int i = 0; i < ans.size(); i++) {
		if(ans[i] >= base1) {
			if(i+1 == (int) ans.size()) ans.pb(0);
			ans[i+1]+= ans[i]/base1;
			ans[i]%= base1;
		}
	}
	while(ans.size() > 1 && ans.back() == 0) ans.pop_back();

	if(geq1(ans,maxt1)) return maxt1;
	return ans;
}

vector<int> trans1(int x) {
	if(x == 0) return vector<int>{0};
	vector<int> ans;
	while(x != 0) {
		ans.pb(x%base1);
		x/= base1;
	}
	return ans;
}

int trans1back1(vector<int> s) {
	int ans = 0;
	int p10 = 1;
	for(int i = 0; i < s.size(); i++) {
		ans+= p10*s[i];
		p10*= base1;
	}
	return ans;
}

vector<int> dp1[260][10*64+10];

void precomp1() {
	maxt1.pb(1);
	for(int i = 0; i <= 40; i++) {
		maxt1.pb(0);
	}
	// dp(i,sum) = # de (q_0,q_1,...,q_i) tal que a soma é no maximo sum
	for(int i = 0; i < R1; i++) {
		for(int j = 0; j <= k1; j++) {
			dp1[i][j] = vector<int>{0};
		}
	}

	for(int j = 0; j <= k1; j++) {
		dp1[0][j] = trans1(j+1);
	}

	for(int i = 1; i < R1; i++) {
		dp1[i][0] = trans1(1);
		for(int j = 1; j <= k1; j++) {
			for(int x = 0; x <= j; x++) {
				dp1[i][j] = add1(dp1[i][j],dp1[i-1][j-x]);
			}
		}
	}
}

vector<int> querysmaller1(vector<int> q) {
	vector<int> ans = {0};

	int sumq = 0;
	for(int i = R1-1; i >= 0; i--) {
		for(int j = 0; j <= q[i]-1 && k1-j-sumq >= 0; j++) {
			if(i == 0) ans = add1(ans,trans1((int)1));
			else ans = add1(ans,dp1[i-1][k1-j-sumq]);
		}
		sumq+= q[i];
	}

	if(sumq <= k1) ans = add1(ans,trans1(1));
	return ans;
}

vector<int> findg1(vector<int> g) {
	vector<int> ans(R1,0);

	int sumans = 0;
	for(int i = R1-1; i >= 0; i--) {
		ans[i] = 0;
		for(int j = 1; j+sumans <= k1; j++) {
			ans[i] = j;
			if(!(geq1(g,querysmaller1(ans)))) {
				ans[i] = j-1;
				break;
			}
		}
		sumans+= ans[i];
	}
	return ans;
}

void decode(int32_t n, int32_t L, int32_t X[])
{
	k1 = 5*n;
	R1 = 55;
	precomp1();
	vector<int> q(R1,0);
	for(int i = 0; i < L; i++) {
		q[X[i]]++;
	}
	vector<int> vm = add1(querysmaller1(q),neg(trans1(1)));


	vector<int> m(n);
	for(int i = n-1; i >= 0; i--) {
		vector<int> p256 = trans1(1);
		for(int j = 0; j < i; j++) {
			p256 = mult1(p256,trans1(256));
		}

		m[i] = 0;
		while(geq1(vm,p256)) {
			m[i]++;
			vm = add1(vm,neg(p256));
		}
	}

	for(int i =0; i < n; i++) {
		output((int32_t) m[i]);
	}

}

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fr first
#define sc second
// #define int long long
// const int maxn = 1e5+10;
// const int inf = 1e18+10;
static vector<int> maxt1;
static int R1;
static int k1;

bool geq1(vector<int> s, vector<int> t) {
	if(s.size() > t.size()) return 1;
	if(t.size() > s.size()) return 0;

	for(int i = (int) s.size() -1; i >= 0; i--) {
		if(s[i] > t[i]) return 1;
		if(t[i] > s[i]) return 0;
	}
	return 1;
}

vector<int> mult1(vector<int> s, vector<int> t) {
	vector<int> ans((int) s.size()+(int) t.size(),0);
	if(s == vector<int>{0} or t == vector<int>{0}) return vector<int>{0};

	for(int i = 0; i < s.size(); i++) {
		for(int j = 0; j < t.size(); j++) {
			ans[i+j]+= s[i]*t[j];
		}
	}

	for(int i = 0; i < ans.size(); i++) {
		if(ans[i] >= 10) {
			if(i+1 == (int) ans.size()) ans.pb(0);
			ans[i+1]+= ans[i]/10;
			ans[i]%= 10;
		}
	}
	while(ans.size() > 1 && ans.back() == 0) ans.pop_back();
	if(geq1(ans,maxt1)) return maxt1;
	return ans;
}

vector<int> neg(vector<int> s) {
	for(int i = 0; i < s.size(); i++) {
		s[i]*= -1;
	}
	return s;
}

vector<int> add1(vector<int> s, vector<int> t) {
	vector<int> ans = s;

	for(int i = 0; i < t.size(); i++) {
		if(i == (int) ans.size()) ans.pb(0);
		ans[i]+= t[i];
	}

	for(int i = 0; i < ans.size(); i++) {
		if(ans[i] >= 10) {
			if(i+1 == (int) ans.size()) ans.pb(0);
			ans[i+1]+= ans[i]/10;
			ans[i]%= 10;
		}

		// if(ans[i] <= -10) {
		// 	if(i+1 == (int) ans.size()) ans.pb(0);
		// 	ans[i+1]+= ans[i]/10;
		// 	ans[i]%= 10;
		// }
	}

	for(int i = 0; i+1 < ans.size(); i++) {
		while(ans[i] < 0) {
			ans[i]+= 10;
			ans[i+1]-= 1;
		}
	}
	for(int i = 0; i < ans.size(); i++) {
		if(ans[i] >= 10) {
			if(i+1 == (int) ans.size()) ans.pb(0);
			ans[i+1]+= ans[i]/10;
			ans[i]%= 10;
		}
	}
	while(ans.size() > 1 && ans.back() == 0) ans.pop_back();

	if(geq1(ans,maxt1)) return maxt1;
	return ans;
}

vector<int> trans1(int x) {
	if(x == 0) return vector<int>{0};
	vector<int> ans;
	while(x != 0) {
		ans.pb(x%10);
		x/= 10;
	}
	return ans;
}

int trans1back1(vector<int> s) {
	int ans = 0;
	int p10 = 1;
	for(int i = 0; i < s.size(); i++) {
		ans+= p10*s[i];
		p10*= 10;
	}
	return ans;
}

vector<int> dp1[260][10*64+10];

void precomp1() {
	maxt1.pb(1);
	for(int i = 0; i <= 40; i++) {
		maxt1.pb(0);
	}
	// dp(i,sum) = # de (q_0,q_1,...,q_i) tal que a soma é no maximo sum
	for(int i = 0; i < R1; i++) {
		for(int j = 0; j <= k1; j++) {
			dp1[i][j] = vector<int>{0};
		}
	}

	for(int j = 0; j <= k1; j++) {
		dp1[0][j] = trans1(j+1);
	}

	for(int i = 1; i < R1; i++) {
		dp1[i][0] = trans1(1);
		for(int j = 1; j <= k1; j++) {
			for(int x = 0; x <= j; x++) {
				dp1[i][j] = add1(dp1[i][j],dp1[i-1][j-x]);
			}
		}
	}
}

vector<int> querysmaller1(vector<int> q) {
	vector<int> ans = {0};

	int sumq = 0;
	for(int i = R1-1; i >= 0; i--) {
		for(int j = 0; j <= q[i]-1 && k1-j-sumq >= 0; j++) {
			if(i == 0) ans = add1(ans,trans1((int)1));
			else ans = add1(ans,dp1[i-1][k1-j-sumq]);
		}
		sumq+= q[i];
	}

	if(sumq <= k1) ans = add1(ans,trans1(1));
	return ans;
}

vector<int> findg1(vector<int> g) {
	vector<int> ans(R1,0);

	int sumans = 0;
	for(int i = R1-1; i >= 0; i--) {
		ans[i] = 0;
		for(int j = 1; j+sumans <= k1; j++) {
			ans[i] = j;
			if(!(geq1(g,querysmaller1(ans)))) {
				ans[i] = j-1;
				break;
			}
		}
		sumans+= ans[i];
	}
	return ans;
}

void decode(int n, int L, int X[])
{
	k1 = 5*n;
	R1 = 60;
	precomp1();
	vector<int> q(R1,0);
	for(int i = 0; i < L; i++) {
		q[X[i]]++;
	}
	vector<int> vm = add1(querysmaller1(q),neg(trans1(1)));


	vector<int> m(n);
	for(int i = n-1; i >= 0; i--) {
		vector<int> p256 = trans1(1);
		for(int j = 0; j < i; j++) {
			p256 = mult1(p256,trans1(256));
		}

		m[i] = 0;
		while(geq1(vm,p256)) {
			m[i]++;
			vm = add1(vm,neg(p256));
		}
	}

	for(int i =0; i < n; i++) {
		output(m[i]);
	}

}

Compilation message (stderr)

encoder.cpp: In function 'std::vector<long long int> mult1(std::vector<long long int>, std::vector<long long int>)':
encoder.cpp:32:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int i = 0; i < s.size(); i++) {
      |                 ~~^~~~~~~~~~
encoder.cpp:33:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int j = 0; j < t.size(); j++) {
      |                  ~~^~~~~~~~~~
encoder.cpp:38:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(int i = 0; i < ans.size(); i++) {
      |                 ~~^~~~~~~~~~~~
encoder.cpp: In function 'std::vector<long long int> neg(std::vector<long long int>)':
encoder.cpp:51:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i = 0; i < s.size(); i++) {
      |                 ~~^~~~~~~~~~
encoder.cpp: In function 'std::vector<long long int> add1(std::vector<long long int>, std::vector<long long int>)':
encoder.cpp:60:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(int i = 0; i < t.size(); i++) {
      |                 ~~^~~~~~~~~~
encoder.cpp:65:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i = 0; i < ans.size(); i++) {
      |                 ~~^~~~~~~~~~~~
encoder.cpp:79:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i = 0; i+1 < ans.size(); i++) {
      |                 ~~~~^~~~~~~~~~~~
encoder.cpp:85:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for(int i = 0; i < ans.size(); i++) {
      |                 ~~^~~~~~~~~~~~
encoder.cpp: In function 'long long int trans1back1(std::vector<long long int>)':
encoder.cpp:111:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for(int i = 0; i < s.size(); i++) {
      |                 ~~^~~~~~~~~~
/usr/bin/ld: /tmp/ccIhgc7d.o: in function `decode(int, int, int*)':
encoder.cpp:(.text+0x2b75): undefined reference to `output(int)'
/usr/bin/ld: /tmp/ccHYPAmf.o: in function `main':
grader_encoder.cpp:(.text.startup+0x162): undefined reference to `encode(int, int*)'
collect2: error: ld returned 1 exit status

decoder.cpp: In function 'std::vector<int> mult1(std::vector<int>, std::vector<int>)':
decoder.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0; i < s.size(); i++) {
      |                 ~~^~~~~~~~~~
decoder.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int j = 0; j < t.size(); j++) {
      |                  ~~^~~~~~~~~~
decoder.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i = 0; i < ans.size(); i++) {
      |                 ~~^~~~~~~~~~~~
decoder.cpp: In function 'std::vector<int> neg(std::vector<int>)':
decoder.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i = 0; i < s.size(); i++) {
      |                 ~~^~~~~~~~~~
decoder.cpp: In function 'std::vector<int> add1(std::vector<int>, std::vector<int>)':
decoder.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 0; i < t.size(); i++) {
      |                 ~~^~~~~~~~~~
decoder.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i = 0; i < ans.size(); i++) {
      |                 ~~^~~~~~~~~~~~
decoder.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i = 0; i+1 < ans.size(); i++) {
      |                 ~~~~^~~~~~~~~~~~
decoder.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i = 0; i < ans.size(); i++) {
      |                 ~~^~~~~~~~~~~~
decoder.cpp: In function 'int trans1back1(std::vector<int>)':
decoder.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |  for(int i = 0; i < s.size(); i++) {
      |                 ~~^~~~~~~~~~