제출 #143077

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
143077		model_code	Arranging Shoes (IOI19_shoes)	Java	100 / 100	263 ms	16512 KiB

shoes

class shoes {

	private void change(int[] v) {
		int n = v.length / 2;

		int[] cnt = new int[n];
		for(int i = 0; i < n; i++)
			cnt[i] = 0;

		for(int i = 0; i < 2*n; i++)
			if(v[i] > 0)
				cnt[v[i] - 1]++;

		for(int i = 1; i < n; i++)
			cnt[i] += cnt[i-1];


		int[] cntl = new int[n];
		int[] cntr = new int[n];
		for(int i = 0; i < n; i++) {
			cntl[i] = cnt[i];
			cntr[i] = cnt[i];
		}

		for(int i = 0; i < 2*n; i++)
			if(v[i] > 0)
				v[i] = (--cntr[v[i] - 1]) + 1;
			else
				v[i] = -((--cntl[-v[i] - 1]) + 1);
	}


    public long count_swaps(int[] in) {
		change(in);

        int n = in.length / 2;
        
        int where[] = new int[n + 1];
        for (int i = 1; i <= n; ++i)
            where[i] = -1;

        for (int i = 0; i != 2 * n; ++i)
            if (where[Math.abs(in[i])] == -1)
                where[Math.abs(in[i])] = i;
        
        long ans = 0;

        int fenw[] = new int[2 * n];
        for (int i = 0; i != 2 * n; ++i)
            fenw[i] = (i + 1) - (i & (i + 1));
        
        for (int pos = 2 * n - 1; pos >= 0; --pos) {
            if (where[Math.abs(in[pos])] == pos)
                continue;

            int i = where[Math.abs(in[pos])];

            int dist = 0;

            for (int p = pos; p >= 0; p = (p & (p + 1)) - 1)
                dist += fenw[p];
            for (int p = i; p >= 0; p = (p & (p + 1)) - 1)
                dist -= fenw[p];
            
            if (in[pos] > 0)
                --dist;

            ans += dist;
            for (int p = i; p < 2 * n; p = p | (p + 1))
                fenw[p] -= 1;
        }
        
        return ans;
    }

    // public static void main(String[] argv) {
    //     shoe sh = new shoe();
    //     int[] test = new int[4];
    //     test[0] = -2;
    //     test[1] = -1;
    //     test[2] = 1;
    //     test[3] = 2;
    //     sh.count_swaps(test);
    // }
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15