oj.uz

Submission #636474

# Submission time Handle Problem Language Result Execution time Memory
636474 2022-08-29T10:37:01 Z Dec0Dedd Permutation Recovery (info1cup17_permutation) C++14
94 / 100
 4000 ms 161312 KB 
#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;
	}
 
	/*</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;
	}
 
	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;
	}
 
	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";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct
2 Correct 15 ms 22228 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct
2 Correct 15 ms 22228 KB Output is correct
3 Correct 20 ms 22396 KB Output is correct
4 Correct 19 ms 22392 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct
2 Correct 15 ms 22228 KB Output is correct
3 Correct 20 ms 22396 KB Output is correct
4 Correct 19 ms 22392 KB Output is correct
5 Correct 1170 ms 39808 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct
2 Correct 15 ms 22228 KB Output is correct
3 Correct 20 ms 22396 KB Output is correct
4 Correct 19 ms 22392 KB Output is correct
5 Correct 1170 ms 39808 KB Output is correct
6 Correct 2458 ms 53280 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct
2 Correct 15 ms 22228 KB Output is correct
3 Correct 20 ms 22396 KB Output is correct
4 Correct 19 ms 22392 KB Output is correct
5 Correct 1170 ms 39808 KB Output is correct
6 Correct 2458 ms 53280 KB Output is correct
7 Correct 2385 ms 55644 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct
2 Correct 15 ms 22228 KB Output is correct
3 Correct 20 ms 22396 KB Output is correct
4 Correct 19 ms 22392 KB Output is correct
5 Correct 1170 ms 39808 KB Output is correct
6 Correct 2458 ms 53280 KB Output is correct
7 Correct 2385 ms 55644 KB Output is correct
8 Correct 2994 ms 161312 KB Output is correct
9 Correct 3777 ms 122744 KB Output is correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct
2 Correct 15 ms 22228 KB Output is correct
3 Correct 20 ms 22396 KB Output is correct
4 Correct 19 ms 22392 KB Output is correct
5 Correct 1170 ms 39808 KB Output is correct
6 Correct 2458 ms 53280 KB Output is correct
7 Correct 2385 ms 55644 KB Output is correct
8 Correct 2994 ms 161312 KB Output is correct
9 Correct 3777 ms 122744 KB Output is correct
10 Execution timed out 4080 ms 160200 KB Time limit exceeded
11 Halted 0 ms 0 KB -