結果

問題 No.366 ロボットソート
コンテスト
ユーザー btk
提出日時 2016-04-23 19:20:06
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 1,597 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,633 ms
コンパイル使用メモリ 172,528 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-29 17:18:37
合計ジャッジ時間 2,572 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;



namespace BIT_{
typedef int BITTYPE;
#define BIT_SIZE 10000
#define MAX_CNT 100
	//int cnt=0;
	//BITTYPE mems[MAX_CNT][BIT_SIZE];
	BITTYPE mem[BIT_SIZE];
};
//[1,n],0は扱えない!
template <typename T>class BIT{
private:
	T* bit;int n;
public:
	BIT(int _n){bit=BIT_::mem;fill(bit,bit+BIT_SIZE,0);n=_n;}
	BIT(T* _table,int _sz,int _n){bit=_table;fill(bit,bit+_sz,0);n=_n;}
	int sum(int i){int s=0;while(i>0){s+=bit[i];i-=i&-i;}return s;}
	int sum(int lb,int ub){return sum(ub)-sum(lb-1);}
	void add(int i,int x){while(i<=n){bit[i]+=x;i+=i&-i;}}
	//v[1]+v[2]+...+v[x]>=wとなる最小のxを求める
	int lowerbound(int w){if(w<=0)return 0;int x=0;for(int k = (1<<(31-__builtin_clz(n))); k >0 ; k>>=1)if(x+k<=n&&bit[x+k]<w){w-=bit[x+k];x+=k;}return x+1;}
	void clear(int sz){fill(bit,bit+sz,0);}
};


int main() {
    int N,K;
    cin >> N >> K;
    assert(1 <= N && N <= 1000);
    assert(1 <= K && K <= 1000);
    vector<vector<int>> a(K);
    for(auto& it : a)it.reserve(N);
	{
		map<int,int> z;
    	for(int i = 0; i < N; i++){
        	int in;
        	cin >> in;
        	a[i % K].push_back(in);
			z[in] = 0;
    	}
		//座圧
		{
			int cnt = 1;
			for(auto& it : z)it.second = cnt++;
			for(auto& it : a)for(auto& jt : it)jt = z[jt];
		}
	}
    int res=0;
	for(auto& b : a){
		BIT<int> bit(N);
		for(auto& it : b){
			res+= bit.sum(it + 1,N);
			bit.add(it,1);
		}
		sort(b.begin(),b.end());
	}
	
	for(int i = 0; i < N - 1; i++)
		if(a[i % K][i / K] > a[(i + 1) % K][(i + 1) / K])
			res = -1;
    cout << res << endl;
    return 0;
}
0