oj.uz

Submission #572590

# Submission time Handle Problem Language Result Execution time Memory
572590 2022-06-04T18:22:31 Z arthur_nascimento Permutation (APIO22_perm) C++17
0 / 100
 0 ms 212 KB 
#include "perm.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pb push_back
using namespace std;

std::vector<int> construct_permutation(long long k)
{
	
    k++;
    ll aux = k, sz = 0;
    
    while(aux)
        aux /= 2, sz++;
        
        
    vector<pii> ans;
    
    for(int i=0;i<sz-1;i++)
        ans.pb({2*i,i+1});
        
    vector<int> dec;
    dec.pb(1);
    
    int x = 1, y = 0, skip = 0;
    
    for(int i=sz-2;i>=0;i--, x += 2, y--){
        
        if((k & (1ll << i)) == 0) continue;
        
        if(skip){
            skip = 0;
            ans.pb({x,dec[dec.size()-2]+1});
            continue;
        }
        
        
        if(dec.size() == 1 || i == 0 || (k & (1ll << (i-1))) == 0){
            
            ans.pb({x,y});
            dec.pb(y);
            
            
        }
        
        else {
    
            skip = 1;
            
        }
        
        
        
    }
    
    for(auto p : ans)
        printf("-> %d %d\n",p.first,p.second);
    
    sort(ans.begin(), ans.end());
    
    int c = 0;
    for(auto &p : ans)  p.first = c++;
    
    c = 0;
    sort(ans.begin(), ans.end(), [](pii i,pii j){
        if(i.second == j.second) return i.first > j.first;
        return i.second < j.second;
    });
    
    for(auto &p : ans)  p.second = c++;
    
    sort(ans.begin(), ans.end());

	vector<int> r;
	for(auto p : ans)
		r.pb(p.second);

    return r;

}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 90.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB secret mismatch
2 Halted 0 ms 0 KB -