Submission #3765453
Source Code Expand
#include <bits/stdc++.h>
#define typeof(x) __typeof__(x)
#define int long long int
#define double long double
#define mod(x) ((x % MOD) + MOD) % MOD
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define SZ(c) (int)((c).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define LB(c,x) (int)(lower_bound(ALL(c),x)-(c).begin())
#define UB(c,x) (int)(upper_bound(ALL(c),x)-(c).begin())
#define COUNT(c,x) UB(c,x)-LB(c,x)
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define EXIST(s,e) (s).find(e)!=(s).end()
#define PB push_back
#define MP make_pair
#define vec vector
#define dump(x) cerr << #x << " = " << (x) << endl;
using namespace std;
typedef pair<int,int> P;
struct edge { int to, cost; };
const int INF = 1e18;
const int MOD = 1e9+7;
template<typename T> ostream& operator << (ostream& s, const vector<T>& v) {
s << "[";
for (int i = 0; i < v.size(); i++) { s << v[i]; if (i < v.size() - 1) s << " "; }
s << "]";
return s;
}
template<typename T1, typename T2> ostream& operator << (ostream& s, const pair<T1,T2>& p) {
s << "(" << p.first << "," << p.second << ")";
return s;
}
template<typename T1, typename T2> ostream& operator << (ostream& s, const map<T1,T2>& m) {
s << "{";
for (auto i = m.begin(); i != m.end(); ++i) {
s << i->first << ":" << i->second;
if (next(i) != m.end()) s << ", ";
}
s << "}";
return s;
}
bool check(vec<vec<int>> A, int x)
{
while (true)
{
rep(i, 0, SZ(A)) {
if (SZ(A[i]) == 0) return false;
}
map<int,int> m;
rep(i, 0, SZ(A)) {
m[A[i][0]]++;
}
set<int> s;
EACH(i, m) {
if (i->second > x) s.insert(i->first);
}
bool flag = true;
rep(i, 0, SZ(A)) {
rep(j, 0, SZ(A[i])) {
if (EXIST(s, A[i][j])) {
A[i].erase(A[i].begin() + j);
flag = false;
}
}
}
if (flag) {
return true;
}
}
}
int binary_search(vec<vec<int>>& A)
{
int m, l = -1, r = 300;
while (r - l > 1) {
m = (l + r) / 2;
if (check(A, m)) {
r = m;
} else {
l = m;
}
}
return r;
}
signed main()
{
int N, M; cin >> N >> M;
vec<vec<int>> A(N, vec<int>(M));
rep(i, 0, N) {
rep(j, 0, M) {
cin >> A[i][j];
}
}
cout << binary_search(A) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Sports Festival |
User |
habara_k |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2784 Byte |
Status |
WA |
Exec Time |
669 ms |
Memory |
1732 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
WA |
6 ms |
256 KB |
subtask_1_04.txt |
AC |
5 ms |
384 KB |
subtask_1_05.txt |
AC |
2 ms |
256 KB |
subtask_1_06.txt |
AC |
13 ms |
720 KB |
subtask_1_07.txt |
AC |
56 ms |
784 KB |
subtask_1_08.txt |
AC |
6 ms |
384 KB |
subtask_1_09.txt |
AC |
2 ms |
256 KB |
subtask_1_10.txt |
AC |
5 ms |
384 KB |
subtask_1_11.txt |
WA |
47 ms |
512 KB |
subtask_1_12.txt |
AC |
3 ms |
256 KB |
subtask_1_13.txt |
AC |
34 ms |
720 KB |
subtask_1_14.txt |
AC |
57 ms |
1712 KB |
subtask_1_15.txt |
WA |
669 ms |
1728 KB |
subtask_1_16.txt |
AC |
55 ms |
1732 KB |
subtask_1_17.txt |
AC |
198 ms |
1720 KB |
subtask_1_18.txt |
AC |
513 ms |
1728 KB |