Submission #534850

#TimeUsernameProblemLanguageResultExecution timeMemory
534850Paul_Liao_1457Group Photo (JOI21_ho_t3)C++14
0 / 100
0 ms204 KiB
// 還要更強 #include<iostream> #include<queue> #include<set> #include<map> #include<iomanip> #include<math.h> #include<cstring> #include<stack> #include<string.h> #include<random> #include<algorithm> #include<vector> #define ll long long #define FOR(i,a,b) for(int i=a;i<b;i++) #define REP(i,a,b) for(int i=a;i>=b;i--) #define INF (ll)(1e9) #define pb push_back #define AC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; int bit[5005],a[5005],b[5005],n,pos[5005]; void add(int x){ for(int i=x;i>0;i-=i&(-i)) bit[i]++; } int ask(int x){ int r=0; for(int i=x;i<=n;i+=i&(-i)){ r+=bit[i]; } return r; } int cnt(){ int ans=0; FOR(i,1,n+1) bit[i]=0; FOR(i,1,n+1){ ans+=ask(b[i]); add(b[i]); } return ans; } bool check(vector<int> v){ FOR(i,1,n)if(v[i]+2<v[i-1]) return 0; return 1; } signed main(){ AC; int res; cin>>n; vector<int> v; FOR(i,1,n+1){ v.pb(i); cin>>a[i]; pos[a[i]]=i; } FOR(i,1,n+1){ b[i]=a[i]; } res=cnt(); do{ if(!check(v)) continue; res=min(res,cnt()); }while(next_permutation(v.begin(),v.end())); cout<<res<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...