Submission #8542247
Source Code Expand
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>
#define MOD 1000000007
#define int long long
//#define PI 3.14159265358979
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template < typename T >
ostream &operator<<(ostream &os, const vector< T > &A) {
for (int i = 0; i < A.size(); i++)
os << A[i] << " ";
os << endl;
return os;
}
template <>
ostream &operator<<(ostream &os, const vector< vector< int > > &A) {
int N = A.size();
int M;
if (N > 0)
M = A[0].size();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++)
os << A[i][j] << " ";
os << endl;
}
return os;
}
typedef pair< int, int > pii;
typedef long long ll;
struct edge {
int from, to, d, c;
edge(int _from = 0, int _to = 0, int _d = 0, int _c = 0) {
from = _from;
to = _to;
d = _d;
c = _c;
}
bool operator<(const edge &rhs) const {
return (d == rhs.d) ? (c < rhs.c) : (d < rhs.d);
}
};
typedef vector< edge > edges;
typedef vector< edges > graph;
struct flow {
int to, cap, rev, cost;
flow(int to = 0, int cap = 0, int rev = 0, int cost = 0) : to(to), cap(cap), rev(rev), cost(cost) {}
};
typedef vector< vector< flow > > flows;
const int di[4] = {0, -1, 0, 1};
const int dj[4] = {-1, 0, 1, 0};
const int ci[5] = {0, 0, -1, 0, 1};
const int cj[5] = {0, -1, 0, 1, 0};
const ll LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const double PI = acos(-1);
template < typename T, typename U >
bool chmin(T &x, const U &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template < typename T, typename U >
bool chmax(T &x, const U &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
struct initializer {
initializer() {
cout << fixed << setprecision(11);
}
};
initializer _____;
int N, M, K, T, Q;
bool check(vector< vector< int > > &A, int k) {
vector< int > idx(N, 0);
vector< int > num(M, 0);
vector< bool > used(M, false);
while (1) {
num.assign(M, 0);
rep(i, N) {
int j = A[i][idx[i]];
while (used[j]) {
j = A[i][++idx[i]];
if (j >= M)
return false;
}
num[j]++;
}
int maxn = 0, maxnj = -1;
rep(j, M) if (chmax(maxn, num[j])) maxnj = j;
used[maxnj] = true;
if (maxn <= k)
return true;
rep(i, N) {
if (A[i][idx[i]] == maxnj) {
idx[i]++;
if (idx[i] >= M)
return false;
}
}
}
}
signed main() {
cin >> N >> M;
vector< vector< int > > A(N, vector< int >(M));
rep(i, N) rep(j, M) {
cin >> A[i][j];
--A[i][j];
}
int l = -1,
r = 310;
while (r - l > 1) {
int m = (l + r) / 2;
if (check(A, m)) {
r = m;
} else {
l = m;
}
}
cout << r << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Sports Festival |
User |
AltTTT |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2993 Byte |
Status |
AC |
Exec Time |
26 ms |
Memory |
1024 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
700 / 700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
AC |
1 ms |
256 KB |
subtask_1_02.txt |
AC |
1 ms |
256 KB |
subtask_1_03.txt |
AC |
2 ms |
256 KB |
subtask_1_04.txt |
AC |
3 ms |
256 KB |
subtask_1_05.txt |
AC |
1 ms |
256 KB |
subtask_1_06.txt |
AC |
6 ms |
512 KB |
subtask_1_07.txt |
AC |
8 ms |
512 KB |
subtask_1_08.txt |
AC |
3 ms |
384 KB |
subtask_1_09.txt |
AC |
1 ms |
256 KB |
subtask_1_10.txt |
AC |
3 ms |
384 KB |
subtask_1_11.txt |
AC |
5 ms |
384 KB |
subtask_1_12.txt |
AC |
2 ms |
256 KB |
subtask_1_13.txt |
AC |
7 ms |
512 KB |
subtask_1_14.txt |
AC |
20 ms |
1024 KB |
subtask_1_15.txt |
AC |
26 ms |
1024 KB |
subtask_1_16.txt |
AC |
21 ms |
1024 KB |
subtask_1_17.txt |
AC |
21 ms |
1024 KB |
subtask_1_18.txt |
AC |
23 ms |
1024 KB |