Submission #298829
Source Code Expand
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstring> #include <cstdio> using namespace std; #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) int b[100020], n; typedef long long ll; typedef pair<int,int> P; ll solve() { // priority_queue<int, vector<int>, greater<int>> Q; vector<P> vp; for (int i = 0; i < n; i++) { vp.push_back(P(b[i], i)); } sort(vp.begin(), vp.end()); ll ans = 0; for(int i = 0; i < n; i++) { P p = vp[i]; int idx = p.second; int val = p.first; //printf("%d,%d\n", val, idx); // l ll lcnt = 0; for (int j = idx - 1; j >= 0; j--) { if (b[j] == -1) continue; //printf("lcnt - %d vs %d\n", val, b[j]); if (val < b[j]) { ++lcnt; } } // r ll rcnt = 0; for (int j = idx + 1; j < n; j++) { if (b[j] == -1) continue; //printf("rcnt - %d vs %d\n", val, b[j]); if (val < b[j]) ++rcnt; } ans += min(lcnt, rcnt); b[idx] = -1; } return ans; } int main() { while (cin >> n) { for(size_t i = 0; i < n; i++) { cin >> b[i]; } printf("%lld\n", solve()); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 積み木 |
User | brly |
Language | C++ (G++ 4.6.4) |
Score | 30 |
Code Size | 1573 Byte |
Status | TLE |
Exec Time | 2033 ms |
Memory | 2340 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 0 / 70 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt |
Subtask1 | 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 10_small_00.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 10_small_10.txt, 10_small_11.txt, 10_small_12.txt, 10_small_13.txt, 10_small_14.txt, 10_small_15.txt, 10_small_16.txt, 10_small_17.txt, 10_small_18.txt, 10_small_19.txt, 10_small_20.txt, 10_small_21.txt, 10_small_22.txt, 10_small_23.txt, 10_small_24.txt, 10_small_25.txt, 10_small_26.txt, 10_small_27.txt, 10_small_28.txt, 10_small_29.txt |
Subtask2 | 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 10_small_00.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 10_small_10.txt, 10_small_11.txt, 10_small_12.txt, 10_small_13.txt, 10_small_14.txt, 10_small_15.txt, 10_small_16.txt, 10_small_17.txt, 10_small_18.txt, 10_small_19.txt, 10_small_20.txt, 10_small_21.txt, 10_small_22.txt, 10_small_23.txt, 10_small_24.txt, 10_small_25.txt, 10_small_26.txt, 10_small_27.txt, 10_small_28.txt, 10_small_29.txt, 20_rand_00.txt, 20_rand_01.txt, 20_rand_02.txt, 20_rand_03.txt, 20_rand_04.txt, 20_rand_05.txt, 20_rand_06.txt, 20_rand_07.txt, 20_rand_08.txt, 20_rand_09.txt, 20_rand_10.txt, 20_rand_11.txt, 20_rand_12.txt, 20_rand_13.txt, 20_rand_14.txt, 20_rand_15.txt, 20_rand_16.txt, 20_rand_17.txt, 20_rand_18.txt, 20_rand_19.txt, 20_rand_20.txt, 20_rand_21.txt, 20_rand_22.txt, 20_rand_23.txt, 20_rand_24.txt, 20_rand_25.txt, 20_rand_26.txt, 20_rand_27.txt, 20_rand_28.txt, 20_rand_29.txt, 30_max_0.txt, 30_max_1.txt, 30_max_2.txt, 30_max_3.txt, 30_max_4.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00.txt | AC | 23 ms | 908 KB |
00_sample_01.txt | AC | 21 ms | 800 KB |
00_sample_02.txt | AC | 24 ms | 700 KB |
10_small_00.txt | AC | 24 ms | 796 KB |
10_small_01.txt | AC | 22 ms | 736 KB |
10_small_02.txt | AC | 23 ms | 800 KB |
10_small_03.txt | AC | 23 ms | 804 KB |
10_small_04.txt | AC | 20 ms | 796 KB |
10_small_05.txt | AC | 22 ms | 924 KB |
10_small_06.txt | AC | 22 ms | 800 KB |
10_small_07.txt | AC | 23 ms | 744 KB |
10_small_08.txt | AC | 24 ms | 796 KB |
10_small_09.txt | AC | 22 ms | 804 KB |
10_small_10.txt | AC | 25 ms | 784 KB |
10_small_11.txt | AC | 22 ms | 924 KB |
10_small_12.txt | AC | 23 ms | 788 KB |
10_small_13.txt | AC | 22 ms | 924 KB |
10_small_14.txt | AC | 24 ms | 796 KB |
10_small_15.txt | AC | 22 ms | 672 KB |
10_small_16.txt | AC | 21 ms | 732 KB |
10_small_17.txt | AC | 23 ms | 924 KB |
10_small_18.txt | AC | 24 ms | 800 KB |
10_small_19.txt | AC | 23 ms | 676 KB |
10_small_20.txt | AC | 22 ms | 804 KB |
10_small_21.txt | AC | 22 ms | 796 KB |
10_small_22.txt | AC | 24 ms | 676 KB |
10_small_23.txt | AC | 22 ms | 800 KB |
10_small_24.txt | AC | 22 ms | 804 KB |
10_small_25.txt | AC | 23 ms | 676 KB |
10_small_26.txt | AC | 23 ms | 736 KB |
10_small_27.txt | AC | 24 ms | 796 KB |
10_small_28.txt | AC | 22 ms | 860 KB |
10_small_29.txt | AC | 22 ms | 800 KB |
20_rand_00.txt | TLE | 2029 ms | 1688 KB |
20_rand_01.txt | AC | 293 ms | 1052 KB |
20_rand_02.txt | AC | 1526 ms | 1184 KB |
20_rand_03.txt | TLE | 2030 ms | 1308 KB |
20_rand_04.txt | TLE | 2031 ms | 2208 KB |
20_rand_05.txt | TLE | 2031 ms | 2272 KB |
20_rand_06.txt | TLE | 2033 ms | 2208 KB |
20_rand_07.txt | TLE | 2030 ms | 2192 KB |
20_rand_08.txt | AC | 1556 ms | 1312 KB |
20_rand_09.txt | AC | 776 ms | 1180 KB |
20_rand_10.txt | TLE | 2031 ms | 1696 KB |
20_rand_11.txt | TLE | 2031 ms | 1308 KB |
20_rand_12.txt | TLE | 2031 ms | 1312 KB |
20_rand_13.txt | TLE | 2030 ms | 1568 KB |
20_rand_14.txt | TLE | 2030 ms | 1316 KB |
20_rand_15.txt | AC | 179 ms | 924 KB |
20_rand_16.txt | TLE | 2031 ms | 1572 KB |
20_rand_17.txt | AC | 78 ms | 924 KB |
20_rand_18.txt | TLE | 2030 ms | 2340 KB |
20_rand_19.txt | AC | 1703 ms | 1192 KB |
20_rand_20.txt | AC | 856 ms | 1060 KB |
20_rand_21.txt | TLE | 2031 ms | 1696 KB |
20_rand_22.txt | TLE | 2030 ms | 1684 KB |
20_rand_23.txt | TLE | 2030 ms | 2204 KB |
20_rand_24.txt | TLE | 2029 ms | 1572 KB |
20_rand_25.txt | TLE | 2031 ms | 1572 KB |
20_rand_26.txt | TLE | 2030 ms | 1560 KB |
20_rand_27.txt | TLE | 2031 ms | 1560 KB |
20_rand_28.txt | TLE | 2030 ms | 2208 KB |
20_rand_29.txt | AC | 789 ms | 1184 KB |
30_max_0.txt | TLE | 2030 ms | 2336 KB |
30_max_1.txt | TLE | 2031 ms | 2332 KB |
30_max_2.txt | TLE | 2031 ms | 2332 KB |
30_max_3.txt | TLE | 2031 ms | 2336 KB |
30_max_4.txt | TLE | 2031 ms | 2336 KB |