Submission #1014497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014497		tuannm	Permutation (APIO22_perm)	C++17	91.33 / 100	2 ms	460 KiB

perm

#include<bits/stdc++.h>
#include "perm.h"
#define pb push_back
using namespace std;

vector<int> construct_permutation(long long k){
    vector<long double> tmp;
    int itr = 0;
    bool used = false;
    long double ngungu = 1.5;
    int pos = 1e9, neg = -1;
    vector<int> xx;
    while(k){
        xx.pb(k % 4);
        k /= 4;
    }
    reverse(xx.begin(), xx.end());
    for(int m : xx){
        if(!itr){
            if(m == 2)
                tmp = {0};
            else if(m == 3){
                tmp = {1, 0};
//                used = true;
            }
        }
        else{
            if(!m){
                tmp.pb(pos);
                tmp.pb(pos + 1);
                pos += 2;
            }
            else if(m == 1){
                tmp.pb(pos);
                tmp.pb(pos + 1);
                tmp.pb(neg);
                pos += 2;
                --neg;
//                used = true;
            }
            else if(m == 2){
                tmp.pb(pos);
                tmp.pb(neg);
                tmp.pb(pos + 1);
                pos += 2;
                --neg;
//                used = true;
            }
            else{
                if(!used){
//                    used = true;
                    tmp.pb(pos);
                    tmp.pb(neg);
                    tmp.pb(pos + 1);
                    tmp.pb(neg - 1);
                    pos += 2;
                    neg -= 2;
                }
//                else{
//                    tmp.pb(pos);
//                    tmp.pb(pos + 1);
//                    tmp.pb(ngungu);
//                    pos += 2;
//                    ngungu += 5.0;
//                }
            }
        }
        ++itr;
    }
    vector<int> ans;
    vector<long double> t1 = tmp;
    sort(t1.begin(), t1.end());
    for(auto &i : tmp)
        ans.pb(i = lower_bound(t1.begin(), t1.end(), i) - t1.begin());
//    for(int i : ans)
//        cout << i << " ";
//    cout << "\n";
    return ans;
}

//static bool check_permutation(vector<int> v)
//{
//	sort(v.begin(),v.end());
//	for(int i=0;i<v.size();i++)
//		if(v[i]!=i) return 0;
//	return 1;
//}
//
//long long count_increasing(const vector<int>& v) {
//  vector<long long> dp(v.size() + 1, 0);
//  dp[0] = 1;
//  for (int x : v)
//  {
//  	for (int i = 0; i <= x; i++)
//  	{
//  		dp[x+1] += dp[i];
//  		dp[x+1] = min(dp[x+1],1000000000000000001);
//  	}
//  }
//  long long result = 0;
//  for (int i = 0; i <= (int)v.size(); i++){
//  	result += dp[i];
//  	result = min(result,1000000000000000001);
//  }
//  return result;
//}
//
//
//int main(){
//    long long k;
//    cin >> k;
//    vector<int> v = construct_permutation(k);
//    if(!check_permutation(v)){
//        cout << k << " Not a permutation.";
//        return 0;
//    }
//    if(count_increasing(v) != k){
//        cout << "Differ.\n";
//        cout << k << " " << count_increasing(v) << "\n";
//        return 0;
//    }
//}

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:10:17: warning: unused variable 'ngungu' [-Wunused-variable]
   10 |     long double ngungu = 1.5;
      |                 ^~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 81.333333333 / 90