oj.uz

답안 #67879

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
67879 2018-08-15T11:37:40 Z cdemirer Permutation Recovery (info1cup17_permutation) C++17
25 / 100
 7 ms 484 KB 
#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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 7 ms 484 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 7 ms 484 KB Output is correct
3 Runtime error 3 ms 484 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 7 ms 484 KB Output is correct
3 Runtime error 3 ms 484 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 7 ms 484 KB Output is correct
3 Runtime error 3 ms 484 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 7 ms 484 KB Output is correct
3 Runtime error 3 ms 484 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 7 ms 484 KB Output is correct
3 Runtime error 3 ms 484 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 7 ms 484 KB Output is correct
3 Runtime error 3 ms 484 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -