Submission #1146921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146921		Alihan_8	Permutation Recovery (info1cup17_permutation)	C++20	0 / 100	1093 ms	21956 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define siz(x) (int)(x).size()

struct big_num{
	vector <int> d;
	
	big_num(int x = 0){
		do{
			d.push_back(x % 10);
			x /= 10;
		} while ( x > 0 );
	}
	
	big_num(vector <int> d) : d(d) {
		while ( siz(d) > 1 && !d.back() ) d.pop_back();
	}
	
	big_num(string s){
		d.resize(siz(s));
		
		for ( int i = 0; i < siz(d); i++ ){
			d[i] = s[siz(s) - i - 1] - '0';
		}
	}
	
	big_num operator +(const big_num &q){
		vector <int> ret(max(siz(d), siz(q.d)));
		
		int v = 0;
		
		for ( int i = 0; i < siz(ret); i++ ){
			int x = (siz(d) > i ? d[i] : 0) + (siz(q.d) > i ? q.d[i] : 0) + v;
			
			ret[i] = x % 10;
			v = x / 10;
		}
		
		if ( v != 0 ) ret.push_back(v);
		
		return big_num(ret);
	}
	
	bool operator ==(const big_num &q){ return d == q.d; } 
	
	bool operator >(const big_num &q){
		if ( *this == q ) return false;
		
		if ( siz(q.d) != siz(d) ) return siz(d) > siz(q.d);
		
		for ( int i = 0; i < siz(d); i++ ){
			if ( q.d[i] != d[i] ) return d[i] > q.d[i];
		} assert(false);
	}
	
	bool operator <(const big_num &q){
		return !(*this == q) && !(*this > q);
	}
	
	void print(){
		for ( int i = siz(d) - 1; i >= 0; i-- ) cout << d[i] << ' ';
		cout << '\n';
	}
};

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n; cin >> n;
	
	vector <big_num> q(n);
	
	for ( int i = 0; i < n; i++ ){
		string s; cin >> s;
		
		q[i] = big_num(s);
	}
	
	vector <big_num> dp(n);
	vector <int> p;
	
	big_num pf;
	
	for ( int i = 0; i < n; i++ ){
		dp[i] = {1};
		
		int j = 0;
		
		for (; j < siz(p); j++ ){
			if ( dp[i] + pf == q[i] ) break;
			
			dp[i] = dp[i] + dp[p[j]];
		}
		
		assert(dp[i] + pf == q[i]);
		
		pf = pf + dp[i];
		
		p.push_back(i);
		
		for ( int k = i; k > j; k-- ) swap(p[k], p[k - 1]);
	}
	
	vector <int> pos(n);
	
	for ( int i = 0; i < n; i++ ) pos[p[i]] = i;
	
	for ( auto &x: pos ) cout << x + 1 << ' ';
	
	cout << '\n';
};

• Subtask 1: 0 / 100