Submission #636473

# Submission time Handle Problem Language Result Execution time Memory
636473 2022-08-29T10:35:36 Z Dec0Dedd Permutation Recovery (info1cup17_permutation) C++14
0 / 100
359 ms 681984 KB
#include <bits/stdc++.h>

using namespace std;

#define ll long long

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

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;
	}

	/*</arpa>*/
	bigint() :
		sign(1) {
	}
 
	bigint(long long v) {
		*this = v;
	}
 
	bigint(const string &s) {
		read();
	}
 
	void operator=(const bigint &v) {
		sign = v.sign;
		a = v.a;
	}
 
	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 (v.abs() < abs() || 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+=(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 !(*this < v) && !(v < *this);
	}
 
	void trim() {
		while (!a.empty() && !a.back())
			a.pop_back();
		if (a.empty())
			sign = 1;
	}
 
	bigint operator-() const {
		bigint res = *this;
		res.sign = -sign;
		return res;
	}
 
	bigint abs() const {
		bigint res = *this;
		res.sign *= res.sign;
		return res;
	}
 
	void read() {
      string s; cin>>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();
	}
};

#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; lst.read();

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

   for (int i=1; i<=n; ++i) {
      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";
}
# Verdict Execution time Memory Grader output
1 Runtime error 359 ms 681984 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 359 ms 681984 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 359 ms 681984 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 359 ms 681984 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 359 ms 681984 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 359 ms 681984 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 359 ms 681984 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 359 ms 681984 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -