Contest Duration: - (local time) (90 minutes) Back to Home

Submission #33429

Source Code Expand

Copy
```#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

const int MAX_LR = 3010;

int L, R;
bool vis[MAX_LR], usd[MAX_LR];
int lev[MAX_LR + 1], mat[MAX_LR];

bool augment(int l) {
if (l == L) return true;
if (vis[l]) return false;
vis[l] = true;
int r = adj[l][i], l2 = mat[r];
if (lev[l2] > lev[l] && augment(l2)) {
mat[r] = l;
return true;
}
}
return false;
}

int bipartite_matching() {
fill(mat, mat + R, L);
memset(usd, 0, sizeof(bool) * L);
bool update;
do {
fill(lev, lev + L + 1, -1);
lev[L] = R;
queue<int> que;
rep (l, L) if (!usd[l]) {
que.push(l);
lev[l] = 0;
}
while (!que.empty()) {
int l = que.front();
que.pop();
int r = adj[l][i], l2 = mat[r];
if (lev[l2] < 0) {
lev[l2] = lev[l] + 1;
que.push(l2);
}
}
}

memset(vis, 0, sizeof(bool) * L);
update = false;
rep (l, L) if (!usd[l] && augment(l)) usd[l] = update = true;
} while (update);

return count(usd, usd + L, true);
}

int main() {
int N;
while (1 == scanf("%d", &N)) {
vector<int> W(N);
rep (i, N) scanf("%d", &W[i]);

L = R = N;
rep (l, N) rep (r, N) {
if (l < r && W[l] >= W[r]) adj[l].pb(r);
}
printf("%d\n", N - bipartite_matching());
}

return 0;
}
```

#### Submission Info

Submission Time 2012-07-21 20:16:23+0900 C - 積み重ね iwiwi C++ (G++ 4.6.4) 100 2091 Byte AC 80 ms 948 KB

#### Compile Error

```./Main.cpp: In function ‘int main()’:
./Main.cpp:87:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
```

#### Judge Result

Set Name All
Score / Max Score 100 / 100
Status
 AC × 44
Set Name Test Cases
All 00_min.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 02_maxrnd_00.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_increase_00.txt, 03_increase_01.txt, 03_increase_02.txt, 04_decrease_00.txt, 04_decrease_01.txt, 04_decrease_02.txt, 05_same_00.txt, 05_same_01.txt
Case Name Status Exec Time Memory
00_min.txt AC 21 ms 792 KB
00_sample_01.txt AC 21 ms 920 KB
00_sample_02.txt AC 21 ms 792 KB
00_sample_03.txt AC 22 ms 948 KB
00_sample_04.txt AC 21 ms 796 KB
00_sample_05.txt AC 22 ms 792 KB
01_rnd_00.txt AC 21 ms 792 KB
01_rnd_01.txt AC 21 ms 912 KB
01_rnd_02.txt AC 21 ms 784 KB
01_rnd_03.txt AC 21 ms 920 KB
01_rnd_04.txt AC 21 ms 916 KB
01_rnd_05.txt AC 21 ms 920 KB
01_rnd_06.txt AC 21 ms 916 KB
01_rnd_07.txt AC 21 ms 916 KB
01_rnd_08.txt AC 21 ms 892 KB
01_rnd_09.txt AC 21 ms 888 KB
02_maxrnd_00.txt AC 20 ms 920 KB
02_maxrnd_01.txt AC 20 ms 920 KB
02_maxrnd_02.txt AC 21 ms 860 KB
02_maxrnd_03.txt AC 21 ms 944 KB
02_maxrnd_04.txt AC 21 ms 912 KB
02_maxrnd_05.txt AC 22 ms 868 KB
02_maxrnd_06.txt AC 21 ms 916 KB
02_maxrnd_07.txt AC 21 ms 876 KB
02_maxrnd_08.txt AC 23 ms 884 KB
02_maxrnd_09.txt AC 21 ms 912 KB
02_maxrnd_10.txt AC 20 ms 916 KB
02_maxrnd_11.txt AC 20 ms 916 KB
02_maxrnd_12.txt AC 20 ms 912 KB
02_maxrnd_13.txt AC 22 ms 892 KB
02_maxrnd_14.txt AC 21 ms 864 KB
02_maxrnd_15.txt AC 21 ms 920 KB
02_maxrnd_16.txt AC 21 ms 916 KB
02_maxrnd_17.txt AC 21 ms 792 KB
02_maxrnd_18.txt AC 21 ms 920 KB
02_maxrnd_19.txt AC 21 ms 916 KB
03_increase_00.txt AC 21 ms 912 KB
03_increase_01.txt AC 21 ms 892 KB
03_increase_02.txt AC 21 ms 796 KB
04_decrease_00.txt AC 21 ms 912 KB
04_decrease_01.txt AC 21 ms 920 KB
04_decrease_02.txt AC 80 ms 916 KB
05_same_00.txt AC 20 ms 916 KB
05_same_01.txt AC 20 ms 920 KB