結果

問題 No.2089 置換の符号
ユーザー KKT89KKT89
提出日時 2022-09-30 21:46:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 1,741 bytes
コンパイル時間 1,444 ms
コンパイル使用メモリ 135,580 KB
最終ジャッジ日時 2025-02-07 19:21:35
ジャッジサーバーID
(参考情報)
judge2 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
#include <deque>
#include <stack>
#include <sstream>
#include <utility>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <array>
#include <bitset>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
inline double time() {
return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}
// 1-indexed
template<typename T>
struct BIT{
int n;
vector<T> bit;
BIT(int n_=0):n(n_),bit(n+1){}
T sum(int i){
T res=0;
for(;i>0;i-=(i&-i))res+=bit[i];
return res;
}
void add(int i,T a){
if(i==0)return;
for(;i<=n;i+=(i&-i)){bit[i]+=a;}
}
int lower_bound(T k){ // k<=sum(res)
if(k<=0)return 0;
int res=0,i=1;
while((i<<1)<=n)i<<=1;
for(;i;i>>=1){
if(res+i<=n&&bit[res+i]<k)k-=bit[res+=i];
}
return res+1;
}
};
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n; cin >> n;
vector<int> a(n);
for(int i=0;i<n;i++){
cin >> a[i];
}
ll res=0;
BIT<int> bit(n);
for(int i=0;i<n;i++){
res+=i-bit.sum(a[i]);
bit.add(a[i],1);
}
if(res%2 == 0){
cout << 1 << endl;
}
else{
cout << -1 << endl;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0