Submission #1014496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014496		tuannm	Permutation (APIO22_perm)	C++17	0 / 100	0 ms	348 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;
//    }
//}

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