Submission #67879

#	Time	Username	Problem	Language	Result	Execution time	Memory
67879		cdemirer	Permutation Recovery (info1cup17_permutation)	C++17	25 / 100	7 ms	484 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef pair<double, double> dodo;
typedef pair<ll, ll> llp;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)


ll N;
ll arr[400];
vector<pair<double, llp> > V;
int ans[400];

void makeitgood() {
	set<double> S;
	for (int i = 0; i < V.size(); i++) {
		S.insert(V[i].first);
	}
	double cnt = 0.0;
	map<double, double> M;
	while (!S.empty()) {
		M[*S.begin()] = cnt;
		S.erase(S.begin());
		cnt += 1.0;
	}
	for (int i = 0; i < V.size(); i++) {
		V[i].first = M[ V[i].first ];
	}
}

int main(int argc, char **argv) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	if (N > 400) exit(-1);
	
	for (int i = 0; i < N; i++) cin >> arr[i];
	
	V.pb(mp(0.0, mp(0, -1)));
	V.pb(mp(1.0, mp(0, -1)));
	
	for (int i = 0; i < N; i++) {
		
		/*for (int k = 0; k < V.size(); k++) {
			cerr << V[k].first << " " << V[k].second.first << " " << V[k].second.second << endl;
		} cerr << endl;*/
		
		ll d = (i?arr[i]-arr[i-1]:arr[i]);
		ll presum = 0;
		int ptr = 0;
		while (presum + 1 != d) {
			//cerr << presum+1 << " " << d << endl;
			presum += V[ptr].second.first;
			ptr++;
		}
		if (ptr != 0) ptr--;
		double key = (V[ptr].first + V[ptr+1].first) / 2.0;
		//cerr << "inserting with key: " << key << "  " << V[ptr].first << " - " << V[ptr+1].first << " . " << ptr << endl;
		V.insert(V.begin()+ptr+1, mp(key, mp(d, i)));
		sort(V.begin(), V.end());
		if (i % 10 == 0) {
			makeitgood();
		}
	}
	/*for (int k = 0; k < V.size(); k++) {
		cerr << V[k].first << " " << V[k].second.first << " " << V[k].second.second << endl;
	} cerr << endl;*/
	makeitgood();
	for (int i = 0; i < V.size(); i++) {
		if (V[i].second.second != -1) ans[ V[i].second.second ] = V[i].first;
	}
	for (int i = 0; i < N; i++) {
		cout << ans[i] << " ";
	}
	cout << endl;

	return 0;
}

Compilation message (stderr)

permutation.cpp: In function 'void makeitgood()':
permutation.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) {
                  ~~^~~~~~~~~~
permutation.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) {
                  ~~^~~~~~~~~~
permutation.cpp: In function 'int main(int, char**)':
permutation.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) {
                  ~~^~~~~~~~~~

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