Submission #1334403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1334403		SmuggingSpun	Grid Coloring (JOI25_ho_t1)	C++20	100 / 100	1368 ms	59932 KiB

Main

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
typedef long long ll;
template<class T>bool maximize(T& a, T b){
  if(a < b){
    a = b;
    return true;
  }
  return false;
}
int n;
namespace sub12{
  void solve(){
    vector<vector<int>>f(n + 1, vector<int>(n + 1));
    map<int, int>cnt;
    for(int i = 1; i <= n; cnt[f[i++][1]]++){
      cin >> f[i][1];
    }
    for(int i = 1; i <= n; cnt[f[1][i++]]++){
      cin >> f[1][i];
    }
    cnt[f[1][1]]--;
    for(int i = 2; i <= n; i++){
      for(int j = 2; j <= n; j++){
        cnt[f[i][j] = max(f[i][j - 1], f[i - 1][j])]++;
      }
    }
    int ans, best = -1;
    for(auto& [u, v] : cnt){
      maximize(best, v);
      if(best == v){
        ans = u;
      }
    }
    cout << ans << " " << best;
  }
}
namespace sub345{
  void solve(){
    vector<int>a(n + 1), b(n + 1), val;
    map<int, int>pa, pb, cnt;
    for(int i = 1; i <= n; cnt[a[i++]]++){
      cin >> a[i];
      if(i > 1 && pa[a[i]] == 0){
        val.push_back(a[pa[a[i]] = i]);
      }
    }
    for(int i = 1; i <= n; cnt[b[i++]]++){
      cin >> b[i];
      if(i > 1 && pb[b[i]] == 0){
        val.push_back(b[pb[b[i]] = i]);
      }
      if(pa[b[i]] == 0){
        pa[b[i]] = n + 1;
      }
    }
    for(int i = 1; i <= n; i++){
      if(pb[a[i]] == 0){
        pb[a[i]] = n + 1;
      }
    }
    cnt[a[1]]--;
    val.push_back(a[1]);
    sort(val.begin(), val.end(), greater<int>());
    val.resize(unique(val.begin(), val.end()) - val.begin());
    int pre_a = n, pre_b = n, ans_val;
    ll ans_cnt = -1;
    for(int& x : val){
      int pia = min(pa[x], pre_a + 1), pib = min(pb[x], pre_b + 1);
      if(maximize(ans_cnt, ll(pre_b - pib + 1) * (pre_a - 1) + ll(pre_a - pia + 1) * (pre_b - 1) - ll(pre_b - pib + 1) * (pre_a - pia + 1) + cnt[x])){
        ans_val = x;
      }
      pre_a = pia - 1;
      pre_b = pib - 1;
    }
    cout << ans_val << " " << ans_cnt;
  }
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
  cin >> n;
  if(n <= 500){
    sub12::solve();
  }
  else{
    sub345::solve();
  }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:83:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25
• Subtask 6: 30 / 30