oj.uz

Submission #911276

# Submission time Handle Problem Language Result Execution time Memory
911276 2024-01-18T17:34:48 Z tosivanmak Permutation (APIO22_perm) C++17
91.3333 / 100
 2 ms 504 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll Log=15;
#define MAX 1e18
#define MOD 1000000007
typedef pair<ll,ll> LP;
#define ld long double

static long long MX=1e18;
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],MX+1);
  	}
  }
  long long result = 0;
  for (int i = 0; i <= (int)v.size(); i++){
  	result += dp[i];
  	result = min(result,MX+1);
  }
  return result;
}
vector<ll>seq;
ll cur=1;
void bm(ll num){
    if(num==0){
        return;
    }
    if(num&1){
        bm(num/2);
        seq.push_back(cur);
        cur++;
    }
    else{
        bm((num-1)/2);
        seq.push_back(cur);
        seq.push_back(-cur);
        cur++;
    }
}
vector<int> construct_permutation(ll n){
   bm(n-1);
//    cout<<seq.size()<<'\n';
   vector<ll>seq2;
   for(auto& u: seq){
       seq2.push_back(u);
   }
   sort(seq2.begin(),seq2.end());
   vector<int>ans;
   for(auto& u: seq){
       ans.push_back(lower_bound(seq2.begin(),seq2.end(),u)-seq2.begin());
   }
   cur=1;
   seq.clear();
   return ans;
}


// int main(){
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL); cout.tie(NULL);
//     ll t=1;
//     // cin>>t; //Remove if 1 testcase
//     for(int n=1;n<=90;n++){
//        vector<int>lol=construct_permutation(n);
//        for(auto& u: lol){
//            cout<<u<<" ";
//        }
//        cout<<count_increasing(lol)<<'\n';
//     }
// }

Compilation message

perm.cpp: In function 'bool check_permutation(std::vector<int>)':
perm.cpp:14:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i=0;i<v.size();i++)
      |              ~^~~~~~~~~
perm.cpp: At global scope:
perm.cpp:11:13: warning: 'bool check_permutation(std::vector<int>)' defined but not used [-Wunused-function]
   11 | static bool check_permutation(vector<int> v)
      |             ^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
81.333333333 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 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 344 KB Output is correct
5 Partially correct 1 ms 348 KB Partially correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Partially correct 2 ms 348 KB Partially correct
9 Correct 1 ms 472 KB Output is correct
10 Partially correct 2 ms 348 KB Partially correct
11 Partially correct 2 ms 348 KB Partially correct
12 Partially correct 2 ms 348 KB Partially correct
13 Partially correct 2 ms 344 KB Partially correct