Submission #636455

#	Time	Username	Problem	Language	Result	Execution time	Memory
636455		Dec0Dedd	Permutation Recovery (info1cup17_permutation)	C++14	78 / 100	4062 ms	247552 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int base = 1000000000;
const int base_digits = 9; 
struct bigint {
	vector<int> a;
	int sign;
	/*<arpa>*/
	int size(){
		if(a.empty())return 0;
		int ans=(a.size()-1)*base_digits;
		int ca=a.back();
		while(ca)
			ans++,ca/=10;
		return ans;
	}
	string to_string(){
		stringstream ss;
		ss << *this;
		string s;
		ss >> s;
		return s;
	}
	int sumof(){
		string s = to_string();
		int ans = 0;
		for(auto c : s)  ans += c - '0';
		return ans;
	}

	/*</arpa>*/
	bigint() :
		sign(1) {
	}
 
	bigint(long long v) {
		*this = v;
	}
 
	bigint(const string &s) {
		read(s);
	}
 
	void operator=(const bigint &v) {
		sign = v.sign;
		a = v.a;
	}
 
	void operator=(long long v) {
		sign = 1;
		a.clear();
		if (v < 0)
			sign = -1, v = -v;
		for (; v > 0; v = v / base)
			a.push_back(v % base);
	}
 
	bigint operator+(const bigint &v) const {
		if (sign == v.sign) {
			bigint res = v;
 
			for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
				if (i == (int) res.a.size())
					res.a.push_back(0);
				res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
				carry = res.a[i] >= base;
				if (carry)
					res.a[i] -= base;
			}
			return res;
		}
		return *this - (-v);
	}
 
	bigint operator-(const bigint &v) const {
		if (sign == v.sign) {
			if (abs() >= v.abs()) {
				bigint res = *this;
				for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
					res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
					carry = res.a[i] < 0;
					if (carry)
						res.a[i] += base;
				}
				res.trim();
				return res;
			}
			return -(v - *this);
		}
		return *this + (-v);
	}
 
	void operator*=(int v) {
		if (v < 0)
			sign = -sign, v = -v;
		for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
			if (i == (int) a.size())
				a.push_back(0);
			long long cur = a[i] * (long long) v + carry;
			carry = (int) (cur / base);
			a[i] = (int) (cur % base);
			//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
		}
		trim();
	}
 
	void operator+=(const bigint &v) {
		*this = *this + v;
	}
	void operator-=(const bigint &v) {
		*this = *this - v;
	}
 
	bool operator<(const bigint &v) const {
		if (sign != v.sign)
			return sign < v.sign;
		if (a.size() != v.a.size())
			return a.size() * sign < v.a.size() * v.sign;
		for (int i = a.size() - 1; i >= 0; i--)
			if (a[i] != v.a[i])
				return a[i] * sign < v.a[i] * sign;
		return false;
	}
 
	bool operator>(const bigint &v) const {
		return v < *this;
	}
	bool operator<=(const bigint &v) const {
		return !(v < *this);
	}
	bool operator>=(const bigint &v) const {
		return !(*this < v);
	}
	bool operator==(const bigint &v) const {
		return !(*this < v) && !(v < *this);
	}
	bool operator!=(const bigint &v) const {
		return *this < v || v < *this;
	}
 
	void trim() {
		while (!a.empty() && !a.back())
			a.pop_back();
		if (a.empty())
			sign = 1;
	}
 
	bool isZero() const {
		return a.empty() || (a.size() == 1 && !a[0]);
	}
 
	bigint operator-() const {
		bigint res = *this;
		res.sign = -sign;
		return res;
	}
 
	bigint abs() const {
		bigint res = *this;
		res.sign *= res.sign;
		return res;
	}
 
	long long longValue() const {
		long long res = 0;
		for (int i = a.size() - 1; i >= 0; i--)
			res = res * base + a[i];
		return res * sign;
	}
 
	void read(const string &s) {
		sign = 1;
		a.clear();
		int pos = 0;
		while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
			if (s[pos] == '-')
				sign = -sign;
			++pos;
		}
		for (int i = s.size() - 1; i >= pos; i -= base_digits) {
			int x = 0;
			for (int j = max(pos, i - base_digits + 1); j <= i; j++)
				x = x * 10 + s[j] - '0';
			a.push_back(x);
		}
		trim();
	}
 
	friend istream& operator>>(istream &stream, bigint &v) {
		string s;
		stream >> s;
		v.read(s);
		return stream;
	}
 
	friend ostream& operator<<(ostream &stream, const bigint &v) {
		if (v.sign == -1)
			stream << '-';
		stream << (v.a.empty() ? 0 : v.a.back());
		for (int i = (int) v.a.size() - 2; i >= 0; --i)
			stream << setw(base_digits) << setfill('0') << v.a[i];
		return stream;
	}
};

#define ll long long
#define pii pair<bigint, int>

const int N = 7e4+1;

ll ans[N];
pii T[4*N];
bigint L[4*N], a[N];

bigint zero;
bigint mn=-1;

void push(int v) {
   T[2*v].first+=L[v], T[2*v+1].first+=L[v];
   L[2*v]+=L[v], L[2*v+1]+=L[v];
   L[v]=zero;
}

pii comb(pii a, pii b) {
   if (a.first == b.first) return {a.first, max(a.second, b.second)};
   if (a.first == 0) return a;
   if (b.first == 0) return b;
   if (a.first < 0) return b;
   if (b.first < 0) return a;
   return min(a, b);
}

void upd(int v, int l, int r, int ql, int qr, bigint val) {
   if (l > qr || r < ql) return;
   if (l >= ql && r <= qr) {
      T[v].first-=val, L[v]-=val;
      if (l < r) push(v);
      return;
   }
   int m=(l+r)/2; push(v);
   upd(2*v, l, m, ql, qr, val), upd(2*v+1, m+1, r, ql, qr, val);
   T[v]=comb(T[2*v], T[2*v+1]);
}

void rem(int v, int l, int r, int p) {
   if (l == r) {
      T[v]={mn, l};
      return;
   }
   int m=(l+r)/2; push(v);
   if (p <= m) rem(2*v, l, m, p);
   else rem(2*v+1, m+1, r, p);
   T[v]=comb(T[2*v], T[2*v+1]);
}

void build(int v, int l, int r) {
   if (l == r) {
      T[v]={a[l], l};
      return;
   }
   int m=(l+r)/2;
   build(2*v, l, m), build(2*v+1, m+1, r);
   T[v]=comb(T[2*v], T[2*v+1]);
}

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);
   cout.tie(NULL);

   int n; cin>>n;
   bigint lst; cin>>lst;

   a[1]=lst-1;
   for (int i=2; i<=n; ++i) {
      bigint x; cin>>x;
      bigint nv=x-lst; lst=x;
      a[i]=nv-1;
   }
   build(1, 1, n);

   for (int i=1; i<=n; ++i) {
      assert(T[1].first == zero);
      int x=T[1].second;
      rem(1, 1, n, x);
      upd(1, 1, n, x, n, a[x]+1);
      ans[x]=i;
   }

   for (int i=1; i<=n; ++i) cout<<ans[i]<<" ";
   cout<<"\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 7 / 7
• Subtask 7: 0 / 16
• Subtask 8: 0 / 6