Submission #718360

#TimeUsernameProblemLanguageResultExecution timeMemory
718360lamPermutation (APIO22_perm)C++17
Compilation error
0 ms0 KiB
#include "perm.h" #include <cstdio> #include <vector> #include <cassert> #include <algorithm> #include <stdlib.h> using namespace std; static long long MX=1e18; #include "perm.h" #include <bits/stdc++.h> #define ll long long using namespace std; vector<int> construct_permutation(long long k) { vector <int> res; ll len = log2(k); vector <int> a; for (int i=1; i<=len; i++) a.push_back(i-1); k-=(1LL<<len); while (k>0) { ll it = 0; while ((1LL<<(it+1))<= k) { it++; } k-= (1LL<<it); a.push_back(it); } int n=a.size(); vector <int> d(n+1,0); for (int i=0; i<n; i++) d[a[i]] ++; for (int i=1; i<=n; i++) d[i]+=d[i-1]; res.resize(n); for (int i=0; i<n; i++) res[i] = --d[a[i]]; // for (int i:a) cerr<<i<<' '; cerr<<endl; // for (int i:res) cerr<<i<<' '; cerr<<endl; return res; } 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; } int main() { int t; assert(1 == scanf("%d", &t)); while(t--) { long long k; assert(1 == scanf("%lld",&k)); vector<int> ret=construct_permutation(k); if(!check_permutation(ret)) { printf("WA: Returned array is not a permutation\n"); exit(0); } long long inc=count_increasing(ret); if(inc!=k) { if(inc==MX+1) printf("WA: Expected %lld increasing subsequences, found more than %lld\n",k, MX); else printf("WA: Expected %lld increasing subsequences, found %lld\n",k,inc); exit(0); } printf("%d\n",(int)ret.size()); for(int i=0;i<ret.size();i++) { printf("%d",ret[i]); if(i+1==ret.size()) printf("\n"); else printf(" "); } } return 0; }

Compilation message (stderr)

perm.cpp: In function 'bool check_permutation(std::vector<int>)':
perm.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0;i<v.size();i++)
      |              ~^~~~~~~~~
perm.cpp: In function 'int main()':
perm.cpp:95:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for(int i=0;i<ret.size();i++)
      |               ~^~~~~~~~~~~
perm.cpp:98:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |    if(i+1==ret.size())
      |       ~~~^~~~~~~~~~~~
/usr/bin/ld: /tmp/cciTUn6i.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccjPIZNh.o:perm.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status