oj.uz

Submission #907377

# Submission time Handle Problem Language Result Execution time Memory
907377 2024-01-15T12:43:19 Z Tymond Permutation (APIO22_perm) C++17
100 / 100
 13 ms 600 KB 
#include <bits/stdc++.h>
#include "perm.h"

using namespace std;
using ll = long long;
using ld = long double;

const ld INF = 1e9;

vector<signed> construct_permutation(ll k){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int aktBit = 64 - __builtin_clzll(k);

	vector<ld> ans;
	bool bylo = false;
	while(aktBit > 0){
		aktBit -= 2;
		if(aktBit == -1){
			//został jeden na końcu
			ans.push_back(INF);//n * 2
			if(k & 1){
				ans.push_back(-INF);//n + 1
			}
		}else{
			int kon = (k >> aktBit) & 3;

			if(ans.size() == 0){
				if(kon == 2){
					ans = {0};
				}else{
					ans = {1, 0};
					bylo = true;
				}
			}else{
				if(kon == 0){
					//n * 4
					ans.push_back(INF);
					ans.push_back(INF + 1);
				}else if(kon == 1){
					//n * 4 + 1
					ans.push_back(INF);
					ans.push_back(INF + 1);
					ans.push_back(-INF);
					bylo = true;
				}else if(kon == 2){
					//n * 4 + 2
					ans.push_back(INF);
					ans.push_back(-INF);
					ans.push_back(INF + 1);
					bylo = true;
				}else if(kon == 3){
					//4 * n + 3
					if(bylo){	
						ans.push_back(INF);
						ans.push_back(INF + 1);
						ans.push_back(1.5);
					}else{
						ans.push_back(INF);
						ans.push_back(-INF);
						ans.push_back(INF + 1);
						ans.push_back(-INF - 1);
						bylo = true;
					}
				}
			}
		}
		
		vector<ld> nasz = ans;
		sort(nasz.begin(), nasz.end());

		for (auto &it : ans){
			it = lower_bound(nasz.begin(), nasz.end(), it) - nasz.begin();
		}
	}

	return vector<signed> (ans.begin(), ans.end());
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 4 ms 520 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 13 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 7 ms 600 KB Output is correct
11 Correct 9 ms 532 KB Output is correct
12 Correct 10 ms 348 KB Output is correct
13 Correct 9 ms 512 KB Output is correct