oj.uz

Submission #1088580

# Submission time Handle Problem Language Result Execution time Memory
1088580 2024-09-14T15:48:25 Z vjudge1 Izbori (COCI17_izbori) C++17
80 / 80
 46 ms 6604 KB 
#include <bits/stdc++.h>
#include <fstream>
using namespace std;

// #define int long long
#define endl '\n'
const int mxn = 501;
const int mod = 1e8;
// int dx[] = {0 , 0 , 1 , -1};
// int dy[] = {1 , -1 , 0 , 0};
//DFS
//----------------------------------
// vector<int> adj[mxn];
// int n , m;
// bool vis[mxn];
// int P[mxn];
// int rem[mxn];
// void dfs(int i){
//     vis[i] = 1;
//     for(auto j : adj[i]){
//         if(!vis[j]){
//             P[j] = i;
//             dfs(j);
//         }
//     }
//     return;
// }
//----------------------------------
//Seg-Tree
//----------------------------------
// int Tree[1 << (int)(ceil(log2(mxn))) + 1];
// int N = 1 << (int)(ceil(log2(mxn)));
// int l ,r;
// int Search(int i , int lr , int rr){
//     if(lr >= l and rr <= r){
//         return Tree[i];
//     }
//     if(lr > r or rr < l) return -1;
//     return max(Search(i * 2 , lr , (lr + rr) / 2) , Search(i * 2 + 1 , (lr + rr) / 2 + 1 , rr));
// }
// void update(int i){
//     while(i /= 2){
//         Tree[i] = max(Tree[i * 2] , Tree[i * 2 + 1]);
//     }
//     return;
// }
//----------------------------------
//comp
//----------------------------------
// map<int , int>mp;
// map<int , int>pm;
// void comp(set<int>s)
// {
//     int idx = 0;
//     for(auto i : s){
//         mp[i] = idx;
//         pm[idx] = i;
//         idx ++;
//     }
// }
//----------------------------------
int n , m , k;
vector<int>a;
set<int>glo;
vector<set<int>>subsets;
void rec(int i){
    if(i == a.size()) return;
    glo.insert(a[i]);
    subsets.push_back(glo);
    rec(i + 1);
    glo.erase(a[i]);
    rec(i + 1);
    return;
}
signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  cin >> n >> m >> k;
  set<int>mt;
  subsets.push_back(mt);
  vector<int>vec[n];
  for(int i = 0 ; i < n ; i++){
      for(int j = 0 ; j < m ; j++){
          int x;
          cin >> x;
          vec[i].push_back(x);
      }
  }
  for(int i = 1; i <= m ; i++){
      if(i != k) a.push_back(i);
  }
  rec(0);
  int mn = 1e9;
  for(int i = 0 ; i < subsets.size() ; i++){
      int mx = -1;
      int cnt[m + 5] = {};
      for(int k = 0 ; k < n ; k++){
          for(int j = 0 ; j < vec[k].size() ; j++){
              if(subsets[i].find(vec[k][j]) != subsets[i].end() and !subsets[i].empty()) continue;
              if(mx == -1) mx = vec[k][j];
              cnt[vec[k][j]] ++;
              if(cnt[vec[k][j]] > cnt[mx] || (cnt[vec[k][j]] == cnt[mx] and vec[k][j] < mx)) mx = vec[k][j];
              break;
        }
      }
      if(i == 0) cout << mx << endl;
      if(mx == k){
          int sz = subsets[i].size();
          mn = min(mn , sz);
      }
  }
  cout << mn << endl;
}

Compilation message

izbori.cpp: In function 'void rec(int)':
izbori.cpp:67:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     if(i == a.size()) return;
      |        ~~^~~~~~~~~~~
izbori.cpp: In function 'int main()':
izbori.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::set<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for(int i = 0 ; i < subsets.size() ; i++){
      |                   ~~^~~~~~~~~~~~~~~~
izbori.cpp:97:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |           for(int j = 0 ; j < vec[k].size() ; j++){
      |                           ~~^~~~~~~~~~~~~~~

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 8 ms 6604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 8 ms 1632 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 9 ms 6420 KB Output is correct
9 Correct 7 ms 856 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 4 ms 1036 KB Output is correct
12 Correct 21 ms 3224 KB Output is correct
13 Correct 40 ms 6420 KB Output is correct
14 Correct 18 ms 3224 KB Output is correct
15 Correct 7 ms 856 KB Output is correct
16 Correct 45 ms 6556 KB Output is correct
17 Correct 21 ms 3224 KB Output is correct
18 Correct 40 ms 6420 KB Output is correct
19 Correct 46 ms 6416 KB Output is correct
20 Correct 46 ms 6416 KB Output is correct