제출 #1081006

#제출 시각아이디문제언어결과실행 시간메모리
1081006BABY_GANGSTER순열 (APIO22_perm)C++17
10 / 100
1 ms348 KiB
#pragma GCC optimize("Ofast,unroll-loops") #include<bits/stdc++.h> //#define int long long #define ll long long #define down cout<<'\n'; #define debug cout<<" cucuucucuuu",down #define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0); #define modwwe int t;cin>>t; while(t--) #define bit(i,j) (i>>j&1) #define sobit(a) __builtin_popcountll(a) #define task "test" #define fin(x) freopen(x".inp","r",stdin) #define fou(x) freopen(x".ans","w",stdout) #define pb push_back #define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms"; using namespace std; #define getchar_unlocked getchar inline int scan() { char c = getchar_unlocked(); int x = 0; while(c<'0'||c>'9') { c=getchar_unlocked(); } while(c>='0'&&c<='9') { x=(x<<1)+(x<<3)+c-'0'; c=getchar_unlocked(); } return x; } void phongbeo(); const int inf=1e9; const int mod2=1e9+9; const int mod1=998244353; struct icd { long double a; int b; }; struct ib { int a; int b; }; struct ic { int a,b,c; }; struct id { int a,b,c,d; }; struct ie { int a,b,c,d,e; }; int n,m,s1,s2,s3,s4,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,dem4,l,r,mid; int i,s10,s12; int kk; int el=29; vector<int> construct_permutation(long long k) { set<int> s; vector<int> v; vector<int> v2; vector<int> v3; dem=0; bool de=0; /// xoay chieu 2 con 2^(i-2)*5=2^(i-1)+2^(i-2) /// xoay chieu 2 con xong roi lay toan bo 2^i+2^(i-1) :) /// 2^(x-1)+2^(x-2) for(int i=59; i>=0; --i) { if(bit(k,i)) { v.pb(i); if(dem==0) dem=i; else dem++; } } dem--; if(dem>=90) { v.clear(); dem=0; s5=2; s4=(1ll<<s5)+1; s2=k%s4; k=k/s4; for(int i=59; i>=0; --i) { if(bit(k,i)) { v.pb(i+s5+1); if(dem==0)dem=i+s5+1; else dem++; } } for(int i=s5;i>=0;--i){ if(bit(s2,i)) { v.pb(i); dem++; } } for(int i=0; i<=dem; i++) s.insert(i); reverse(v.begin(),v.end()); for(int i=0; i<v.size(); i++) { if(i+1==v.size()) { for (auto it = s.begin(); it != s.end(); ++it) v3.pb(*it); reverse(v3.begin(),v3.end()); for(auto x:v3) v2.pb(x); } else { auto x=s.begin(); for(int j=1; j<=v[i]; j++) x++; v2.pb(*x); s.erase(x); } } reverse(v2.begin(),v2.end()); for(int i=s5;i>=1;--i) swap(v2[i],v2[i-1]); return v2; } for(int i=0; i<=dem; i++) s.insert(i); reverse(v.begin(),v.end()); for(int i=0; i<v.size(); i++) { if(i+1==v.size()) { for (auto it = s.begin(); it != s.end(); ++it) v3.pb(*it); reverse(v3.begin(),v3.end()); for(auto x:v3) v2.pb(x); } else { auto x=s.begin(); for(int j=1; j<=v[i]; j++) x++; v2.pb(*x); s.erase(x); } } reverse(v2.begin(),v2.end()); return v2; } /* 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; } int main() { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); 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("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; } */

컴파일 시 표준 에러 (stderr) 메시지

perm.cpp:230:21: warning: "/*" within comment [-Wcomment]
  230 |                     /*
      |                      
perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:118:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int i=0; i<v.size(); i++)
      |                      ~^~~~~~~~~
perm.cpp:120:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |             if(i+1==v.size())
      |                ~~~^~~~~~~~~~
perm.cpp:148:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for(int i=0; i<v.size(); i++)
      |                  ~^~~~~~~~~
perm.cpp:150:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         if(i+1==v.size())
      |            ~~~^~~~~~~~~~
perm.cpp:74:10: warning: unused variable 'de' [-Wunused-variable]
   74 |     bool de=0;
      |          ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...