Submission #1014498

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1014498	2024-07-05T04:29:42 Z	tuannm	Permutation (APIO22_perm)	C++17	100 / 100	10 ms	604 KB

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;
    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};
            }
        }
        else{
            if(!m){
                tmp.pb(1e9);
                tmp.pb(1e9 + 1);
            }
            else if(m == 1){
                tmp.pb(1e9);
                tmp.pb(1e9 + 1);
                tmp.pb(-1e9);
            }
            else if(m == 2){
                tmp.pb(1e9);
                tmp.pb(-1e9);
                tmp.pb(1e9 + 1);
            }
            else{
                bool check = false;
                bool g1 = false;
                for(auto i : tmp){
                    if(i == 1)
                        g1 = true;
                    else if(i == 0){
                        check = g1;
                        break;
                    }
                }
                if(!check){
                    tmp.pb(1e9);
                    tmp.pb(-1e9);
                    tmp.pb(1e9 + 1);
                    tmp.pb(-1e9 - 1);
                }
                else{
                    tmp.pb(1e9);
                    tmp.pb(1e9 + 1);
                    tmp.pb(1.5);
                }
            }
        }
        ++itr;
        vector<long double> t1 = tmp;
        sort(t1.begin(), t1.end());
        for(auto &i : tmp)
            i = lower_bound(t1.begin(), t1.end(), i) - t1.begin();

    }
    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

10.0 / 10.0

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

Subtask #2

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	604 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	3 ms	348 KB	Output is correct
6	Correct	4 ms	436 KB	Output is correct
7	Correct	6 ms	344 KB	Output is correct
8	Correct	8 ms	348 KB	Output is correct
9	Correct	4 ms	348 KB	Output is correct
10	Correct	6 ms	348 KB	Output is correct
11	Correct	9 ms	540 KB	Output is correct
12	Correct	9 ms	480 KB	Output is correct
13	Correct	10 ms	348 KB	Output is correct