oj.uz

답안 #269949

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
269949 2020-08-17T11:29:12 Z theStaticMind Permutation Recovery (info1cup17_permutation) C++14
43 / 100
 4000 ms 6768 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define int long long int
using namespace std;

#define rand() (rand() * rand() + rand() + 1)
 
class BigInt{
public:
	int sign;
	string s;

	BigInt() : s("") {}

	BigInt(string x){
		*this = x;
	}

	BigInt(int x){
		*this = to_string(x);
	}

	BigInt negative(){
		BigInt x = *this;

		x.sign *= -1;

		return x;
	}

	BigInt normalize(int newSign){
		for(int a = s.size() - 1; a > 0 && s[a] == '0'; a--)
			s.erase(s.begin() + a);

		sign = (s.size() == 1 && s[0] == '0' ? 1 : newSign);

		return *this;
	}

	void operator =(string x){
		int newSign = (x[0] == '-' ? -1 : 1);

		s = (newSign == -1 ? x.substr(1) : x);

		reverse(s.begin(), s.end());

		this->normalize(newSign);
	}

	bool operator ==(const BigInt &x) const{
		return (s == x.s && sign == x.sign);
	}

	bool operator <(const BigInt &x) const{
		if(sign != x.sign) return sign < x.sign;

		if(s.size() != x.s.size())
			return (sign == 1 ? s.size() < x.s.size() : s.size() > x.s.size());

		for(int a = s.size() - 1; a >= 0; a--) if(s[a] != x.s[a])
			return (sign == 1 ? s[a] < x.s[a] : s[a] > x.s[a]);

		return false;
	}

	bool operator <=(const BigInt &x) const{
		return (*this < x || *this == x);
	}

	bool operator >(const BigInt &x) const{
		return (!(*this < x) && !(*this == x));
	}

	bool operator >=(const BigInt &x) const{
		return (*this > x || *this == x);
	}

	BigInt operator +(BigInt x){
		BigInt curr = *this;

		if(curr.sign != x.sign) return curr - x.negative();

		BigInt res;

		for(int a = 0, carry = 0; a < s.size() || a < x.s.size() || carry; a++){
			carry += (a < curr.s.size() ? curr.s[a] - '0' : 0) + (a < x.s.size() ? x.s[a] - '0' : 0);

			res.s += (carry % 10 + '0');

			carry /= 10;
		}

		return res.normalize(sign);
	}

	BigInt operator -(BigInt x){
		BigInt curr = *this;

		if(curr.sign != x.sign) return curr + x.negative();

		int realSign = curr.sign;

		curr.sign = x.sign = 1;

		if(curr < x) return ( (x - curr).negative()).normalize(-realSign);

		BigInt res;

		for(int a = 0, borrow = 0; a < s.size(); a++){
			borrow = (curr.s[a] - borrow - (a < x.s.size() ? x.s[a] : '0'));

			res.s += (borrow >= 0 ? borrow + '0' : borrow + '0' + 10);

			borrow = (borrow >= 0 ? 0 : 1);
		}

		return res.normalize(realSign);
	}

	BigInt operator *(BigInt x){
		BigInt res("0");

		for(int a = 0, b = s[a] - '0'; a < s.size(); a++, b = s[a] -'0'){
			while(b--) res = (res + x);

			x.s.insert(x.s.begin(), '0');
		}

		return res.normalize(sign * x.sign);
	}

	BigInt operator /(BigInt x){
		if(x.s.size() == 1 && x.s[0] == '0') x.s[0] /= (x.s[0] - '0');

		BigInt temp("0"), res;

		for(int a = 0; a < s.size(); a++)
			res.s += "0";
		
		int newSign = sign * x.sign;

		x.sign = 1;

		for(int a = s.size() - 1; a >= 0; a--){
			temp.s.insert(temp.s.begin(), '0');
			temp = temp + s.substr(a, 1);

			while(!(temp < x)){
				temp = temp - x;
				res.s[a]++;
			}
		}

		return res.normalize(newSign);
	}

	BigInt operator %(BigInt x){
		if(x.s.size() == 1 && x.s[0] == '0') x.s[0] /= (x.s[0] - '0');

		BigInt res("0");

		x.sign = 1;

		for(int a = s.size() - 1; a >= 0; a--){
			res.s.insert(res.s.begin(), '0');

			res = res + s.substr(a, 1);

			while(!(res < x))
				res = res - x;
		}

		return res.normalize(sign);
	}

	// operator string(){
	// 	string ret = s;

	// 	reverse(ret.begin(), ret.end());

	// 	return (sign == -1 ? "-" : "") + s;
	// }

	string toString() const{
		string ret = s;

		reverse(ret.begin(), ret.end());

		return (sign == -1 ? "-" : "") + ret;
	}

	BigInt toBase10(int base){
		BigInt exp(1), res("0"), BASE(base);
		
		for(int a = 0; a < s.size(); a++){
			int curr = (s[a] < '0' || s[a] > '9' ? (toupper(s[a]) - 'A' + 10) : (s[a] - '0'));

			res = res + (exp * BigInt(curr));
			exp = exp * BASE;
		}

		return res.normalize(sign);
	}

	BigInt toBase10(int base, BigInt mod){
		BigInt exp(1), res("0"), BASE(base);
		
		for(int a = 0; a < s.size(); a++){
			int curr = (s[a] < '0' || s[a] > '9' ? (toupper(s[a]) - 'A' + 10) : (s[a] - '0'));

			res = (res + ((exp * BigInt(curr) % mod)) % mod);
			exp = ((exp * BASE) % mod);
		}

		return res.normalize(sign);
	}

	string convertToBase(int base){
		BigInt ZERO(0), BASE(base), x = *this;
		string modes = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

		if(x == ZERO)
			return "0";

		string res = "";

		while(x > ZERO){
			BigInt mod = x % BASE;

			x = x - mod;

			if(x > ZERO)
				x = x / BASE;

			res = modes[stoi(mod.toString())] + res;
		}

		return res;
	}

	BigInt toBase(int base){
		return BigInt(this->convertToBase(base));
	}

	friend ostream &operator <<(ostream &os, const BigInt &x){
		os << x.toString();

		return os;
	}
};


struct Node{
 
	int left, right;
	int key;
	int prior;
	BigInt sum = 0, val = 0;  
	int lazy;

	Node(int k = 0){
		left = right = key = prior = lazy = 0;
		key = k;
	}

	bool operator<(Node& A){
		return key < A.key;
	}
	bool operator==(Node& A){
		return key == A.key;
	}
 
};
 
vector<Node> node;
 
namespace Treap{
 
	int root = 0;
	int ind = 1;
 
	int new_node(){
		return ind++;
	}

	void push(int j){

		if(!j) return;

		int l = node[j].left;
		int r = node[j].right;

		node[j].key += node[j].lazy;

		if(l){
			node[l].lazy += node[j].lazy;
		}

		if(r){
			node[r].lazy += node[j].lazy;
		}

		node[j].lazy = 0;


	}

	void print(int j){
		if(!j)return;
		push(j);

		int l = node[j].left;
		int r = node[j].right;


		if(l){
			print(l);
		}
		if(r){
			print(r);
		}
	}

	void up(int j){

		if(!j) return;

		int l = node[j].left;
		int r = node[j].right;

		node[j].sum = node[l].sum + node[r].sum + node[j].val;

	}

	void split(int j, Node v, int& l, int& r){

		push(j);

		if(!j) l = r = 0;

		else if(node[j] < v){

			split(node[j].right, v, node[j].right, r);

			l = j;

		}

		else{

			split(node[j].left, v, l, node[j].left);
 
			r = j;
 
		}
		
		push(j);
		push(node[j].left);
		push(node[j].right);
		up(j);
 
	}

	void merge(int& j, int l, int r){

		push(l);
		push(r);

		if(!l || !r) j = max(l, r);

		else if(node[l].prior > node[r].prior){

			merge(node[l].right, node[l].right, r);

			j = l;

		} 

		else{

			merge(node[r].left, l, node[r].left);

			j = r;
		}

		push(j);
		push(node[j].left);
		push(node[j].right);
		up(j);

	}

	void insert(int& j, int i){

		push(j);

		if(!j) j = i;

		else if(node[i].prior > node[j].prior){

			split(j, node[i], node[i].left, node[i].right);

			j = i;

		}
		else {
			if(node[i] < node[j]) insert(node[j].left, i);
			else insert(node[j].right, i);
		}
 		push(j);
		push(node[j].left);
		push(node[j].right);
		up(j);
 
	}
	
	int erase(int& j, Node v){

		push(j);

		if(node[j] == v) {
			int ret = j;
			merge(j, node[j].left, node[j].right);
			return ret;
		}
		else{
			if(v < node[j]) return erase(node[j].left, v);
			else return erase(node[j].right, v);
		}
		
		push(node[j].left);
		push(node[j].right);
		up(j);

	}

 
	int add(int v, BigInt t){
		int j = new_node();
		node[j].key = v;
		node[j].prior = rand();
		node[j].sum = node[j].val = t;
		insert(root, j);
		return j;
	}

	int leftmost(int j){
		if(node[j].left) return leftmost(node[j].left);
		return j;
	}
 
 
	void update(int j, BigInt v){
 		
 		int l = 2, r = j;

 		while(l <= r){
 			int m = (l + r) / 2;
 			int tl, tr;
 			split(root, Node(m), tl, tr);
 			if(node[tl].sum < v - 1){
 				l = m + 1;
 			}
 			else if(node[tl].sum == v - 1){
 				root = tl;
 				add(tr ? node[leftmost(tr)].key : j, v);
 				if(tr) node[tr].lazy++;
 				merge(root, root, tr);
 				return;

 			}
 			else r = m - 1;
 			merge(root, tl, tr); 
 		}

 		node[root].lazy++;
 		add(1, v);
	}
	
	void dfs(int j){
		push(j);
		int l = node[j].left;
		int r = node[j].right;
		if(l) dfs(l);
		if(r) dfs(r);

		up(j);
	}
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;

	node = vector<Node> (n + 1);

	BigInt last = 0;
	for(int i = 1; i <= n; i++){
		string t;
		cin >> t;
		BigInt x(t);

		Treap::update(i, x - last);
		last = x;

	}

	Treap::dfs(Treap::root);
	for(int i = 1; i <= n; i++) cout << node[i].key << " ";
}

Compilation message

permutation.cpp: In member function 'BigInt BigInt::operator+(BigInt)':
permutation.cpp:89:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for(int a = 0, carry = 0; a < s.size() || a < x.s.size() || carry; a++){
      |                             ~~^~~~~~~~~~
permutation.cpp:89:47: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for(int a = 0, carry = 0; a < s.size() || a < x.s.size() || carry; a++){
      |                                             ~~^~~~~~~~~~~~
permutation.cpp:90:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |    carry += (a < curr.s.size() ? curr.s[a] - '0' : 0) + (a < x.s.size() ? x.s[a] - '0' : 0);
      |              ~~^~~~~~~~~~~~~~~
permutation.cpp:90:60: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |    carry += (a < curr.s.size() ? curr.s[a] - '0' : 0) + (a < x.s.size() ? x.s[a] - '0' : 0);
      |                                                          ~~^~~~~~~~~~~~
permutation.cpp: In member function 'BigInt BigInt::operator-(BigInt)':
permutation.cpp:113:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int a = 0, borrow = 0; a < s.size(); a++){
      |                              ~~^~~~~~~~~~
permutation.cpp:114:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |    borrow = (curr.s[a] - borrow - (a < x.s.size() ? x.s[a] : '0'));
      |                                    ~~^~~~~~~~~~~~
permutation.cpp: In member function 'BigInt BigInt::operator*(BigInt)':
permutation.cpp:127:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   for(int a = 0, b = s[a] - '0'; a < s.size(); a++, b = s[a] -'0'){
      |                                  ~~^~~~~~~~~~
permutation.cpp: In member function 'BigInt BigInt::operator/(BigInt)':
permutation.cpp:141:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |   for(int a = 0; a < s.size(); a++)
      |                  ~~^~~~~~~~~~
permutation.cpp: In member function 'BigInt BigInt::toBase10(long long int)':
permutation.cpp:199:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |   for(int a = 0; a < s.size(); a++){
      |                  ~~^~~~~~~~~~
permutation.cpp: In member function 'BigInt BigInt::toBase10(long long int, BigInt)':
permutation.cpp:212:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  212 |   for(int a = 0; a < s.size(); a++){
      |                  ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 22 ms 384 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 22 ms 384 KB Output is correct
3 Correct 200 ms 660 KB Output is correct
4 Correct 150 ms 504 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 22 ms 384 KB Output is correct
3 Correct 200 ms 660 KB Output is correct
4 Correct 150 ms 504 KB Output is correct
5 Execution timed out 4045 ms 6768 KB Time limit exceeded

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 22 ms 384 KB Output is correct
3 Correct 200 ms 660 KB Output is correct
4 Correct 150 ms 504 KB Output is correct
5 Execution timed out 4045 ms 6768 KB Time limit exceeded

Subtask #6
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 22 ms 384 KB Output is correct
3 Correct 200 ms 660 KB Output is correct
4 Correct 150 ms 504 KB Output is correct
5 Execution timed out 4045 ms 6768 KB Time limit exceeded

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 22 ms 384 KB Output is correct
3 Correct 200 ms 660 KB Output is correct
4 Correct 150 ms 504 KB Output is correct
5 Execution timed out 4045 ms 6768 KB Time limit exceeded

Subtask #8
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 22 ms 384 KB Output is correct
3 Correct 200 ms 660 KB Output is correct
4 Correct 150 ms 504 KB Output is correct
5 Execution timed out 4045 ms 6768 KB Time limit exceeded