oj.uz

Submission #128958

# Submission time Handle Problem Language Result Execution time Memory
128958 2019-07-11T11:16:28 Z E869120 Permutation Recovery (info1cup17_permutation) C++14
43 / 100
 4000 ms 16244 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
#pragma warning (disable: 4996)

const long long MAX_Z = 10000000000000000LL;

struct BigInteger {
	vector<long long> t;
};

bool operator==(BigInteger a1, BigInteger a2) {
	if (a1.t == a2.t) return true;
	return false;
}

bool operator<(BigInteger a1, BigInteger a2) {
	if (a1.t.size() < a2.t.size()) return true;
	if (a1.t.size() > a2.t.size()) return false;
	for (int i = (int)a1.t.size() - 1; i >= 0; i--) {
		if (a1.t[i] < a2.t[i]) return true;
		if (a1.t[i] > a2.t[i]) return false;
	}
	return true;
}

BigInteger operator+(BigInteger a1, BigInteger a2) {
	BigInteger a3; a3.t.resize(max(a1.t.size(), a2.t.size()) + 1, 0);

	for (int i = 0; i < a1.t.size(); i++) a3.t[i] += a1.t[i];
	for (int i = 0; i < a2.t.size(); i++) a3.t[i] += a2.t[i];
	for (int i = 0; i < (int)a3.t.size() - 1; i++) {
		while (a3.t[i] >= MAX_Z) { a3.t[i] -= MAX_Z; a3.t[i + 1] += 1; }
	}
	while (a3.t.size() >= 2 && a3.t[a3.t.size() - 1] == 0) a3.t.pop_back();
	return a3;
}

BigInteger operator-(BigInteger a1, BigInteger a2) {
	BigInteger a3; a3.t.resize(max(a1.t.size(), a2.t.size()) + 1, 0);

	for (int i = 0; i < a1.t.size(); i++) a3.t[i] += a1.t[i];
	for (int i = 0; i < a2.t.size(); i++) a3.t[i] -= a2.t[i];
	for (int i = 0; i < (int)a3.t.size() - 1; i++) {
		while (a3.t[i] < 0) { a3.t[i] += MAX_Z; a3.t[i + 1] -= 1; }
	}
	while (a3.t.size() >= 2 && a3.t[a3.t.size() - 1] == 0) a3.t.pop_back();
	return a3;
}

BigInteger ConvertFromString(string V) {
	BigInteger a1; a1.t.resize(((int)V.size() + 15) / 16);
	reverse(V.begin(), V.end());
	
	long long r = 1;
	for (int i = 0; i < V.size(); i++) {
		a1.t[i / 16] += r * (long long)(V[i] - '0');
		r *= 10;
		if (i % 16 == 15) r = 1;
	}
	return a1;
}

int N;
BigInteger P[100009], Q[100009]; int A[100009];

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) { string V; cin >> V; P[i] = ConvertFromString(V); }

	for (int i = N; i >= 1; i--) P[i] = (P[i] - P[i - 1]);
	for (int i = 1; i <= N; i++) Q[i] = P[i];
	
	int cnts = 0;
	while (cnts < N) {
		for (int i = N; i >= 1; i--) {
			if (A[i] == 0 && P[i].t == vector<long long>{1LL}) {
				cnts++; A[i] = cnts;
				for (int j = i + 1; j <= N; j++) P[j] = P[j] - Q[i];
				break;
			}
		}
	}

	for (int i = 1; i <= N; i++) { if (i >= 2) cout << " "; cout << A[i]; } cout << endl;
	return 0;
}

Compilation message

permutation.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
permutation.cpp: In function 'BigInteger operator+(BigInteger, BigInteger)':
permutation.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a1.t.size(); i++) a3.t[i] += a1.t[i];
                  ~~^~~~~~~~~~~~~
permutation.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a2.t.size(); i++) a3.t[i] += a2.t[i];
                  ~~^~~~~~~~~~~~~
permutation.cpp: In function 'BigInteger operator-(BigInteger, BigInteger)':
permutation.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a1.t.size(); i++) a3.t[i] += a1.t[i];
                  ~~^~~~~~~~~~~~~
permutation.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a2.t.size(); i++) a3.t[i] -= a2.t[i];
                  ~~^~~~~~~~~~~~~
permutation.cpp: In function 'BigInteger ConvertFromString(std::__cxx11::string)':
permutation.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) {
                  ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 38 ms 5496 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 38 ms 5496 KB Output is correct
3 Correct 90 ms 5636 KB Output is correct
4 Correct 57 ms 5300 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 38 ms 5496 KB Output is correct
3 Correct 90 ms 5636 KB Output is correct
4 Correct 57 ms 5300 KB Output is correct
5 Execution timed out 4097 ms 16244 KB Time limit exceeded

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 38 ms 5496 KB Output is correct
3 Correct 90 ms 5636 KB Output is correct
4 Correct 57 ms 5300 KB Output is correct
5 Execution timed out 4097 ms 16244 KB Time limit exceeded

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 38 ms 5496 KB Output is correct
3 Correct 90 ms 5636 KB Output is correct
4 Correct 57 ms 5300 KB Output is correct
5 Execution timed out 4097 ms 16244 KB Time limit exceeded

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 38 ms 5496 KB Output is correct
3 Correct 90 ms 5636 KB Output is correct
4 Correct 57 ms 5300 KB Output is correct
5 Execution timed out 4097 ms 16244 KB Time limit exceeded

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 38 ms 5496 KB Output is correct
3 Correct 90 ms 5636 KB Output is correct
4 Correct 57 ms 5300 KB Output is correct
5 Execution timed out 4097 ms 16244 KB Time limit exceeded