#88258 (C++11) No.366 ロボットソート

• 問題: No.366 ロボットソート
• ユーザー: btk
• 提出日時: 2016-04-23 19:20:06
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 3 ms / 2,000 ms
• コード長: 1,597 bytes
• コンパイル時間: 1,634 ms
• コンパイル使用メモリ: 173,216 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-09 10:13:49
• 合計ジャッジ時間: 2,369 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	3 ms; 5,376 KB
testcase_12	AC	3 ms; 5,376 KB
testcase_13	AC	3 ms; 5,376 KB
testcase_14	AC	3 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	2 ms; 5,376 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	3 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	2 ms; 5,376 KB

ソースコード

#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;
}