Submission #3765620


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 solve(vec<vec<int>>& A, int x)
{
   rep(i, 0, SZ(A)) {
      if (SZ(A[i]) == 0) return INF;
   }

   map<int,int> m;
   rep(i, 0, SZ(A)) {
      m[A[i][0]]++;
   }

   int MAX = -INF;
   EACH(i, m) {
      MAX = max(MAX, i->second);
   }
   int MIN = min(MAX, x);

   set<int> s;
   EACH(i, m) {
      if (i->second >= MIN) s.insert(i->first);
   }

   rep(i, 0, SZ(A)) {
      rep(j, 0, SZ(A[i])) {
         if (EXIST(s, A[i][j])) {
            A[i].erase(A[i].begin() + j);
         }
      }
   }

   return min(MIN, solve(A, MIN));
}

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 << solve(A, INF) << 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 3131 Byte
Status WA
Exec Time 96 ms
Memory 1408 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 3
AC × 22
WA × 2
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 3 ms 384 KB
subtask_1_04.txt AC 4 ms 384 KB
subtask_1_05.txt AC 2 ms 256 KB
subtask_1_06.txt AC 10 ms 512 KB
subtask_1_07.txt AC 15 ms 512 KB
subtask_1_08.txt AC 4 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 20 ms 640 KB
subtask_1_12.txt AC 3 ms 384 KB
subtask_1_13.txt AC 17 ms 640 KB
subtask_1_14.txt AC 43 ms 1408 KB
subtask_1_15.txt AC 96 ms 1152 KB
subtask_1_16.txt AC 40 ms 1408 KB
subtask_1_17.txt AC 59 ms 1280 KB
subtask_1_18.txt AC 70 ms 1024 KB