Submission #1343852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1343852		SmuggingSpun	Gift Boxes (EGOI25_giftboxes)	C++20	100 / 100	55 ms	4356 KiB

Main

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
template<class T>bool maximize(T& a, T b){
  if(a < b){
    a = b;
    return true;
  }
  return false;
}
const int lim = 5e5 + 5;
int t, n, a[lim];
namespace sub1{
  void solve(){
    vector<bool>p(n + 1, false);
    for(int i = 1; i <= n; i++){
      if(!p[a[i]]){
        p[a[i]] = true;
      }
      else{
        return void(cout << i - 1 << " " << i - 1);
      }
    }
  }
}
namespace sub35{
  const int lim = 5e3 + 5;
  int cnt[lim];
  void solve(){
    int L, R;
    for(int l = 1, best = -1; l <= n; l++){
      memset(cnt, 0, sizeof(cnt));
      for(int i = 1; i <= n; i++){
        cnt[a[i]]++;  
      }
      int other = 0, in = 0;
      for(int i = 0; i < t; i++){
        if(cnt[i] > 1){
          other++;
        }
        else if(cnt[i] == 1){
          in++;
        }
      }
      for(int r = l; r <= n; r++){
        if(--cnt[a[r]] == 1){
          other--;
          in++;
        }
        else if(cnt[a[r]] == 0){
          in--;
        }
        if(other == 0 && maximize(best, in)){
          L = l;
          R = r;
        }
      }
    }
    cout << L - 1 << " " << R - 1;
  }
}
namespace sub246{
  int cnt[lim];
  void solve(){
    int in = 0, other = 0, L, R;
    memset(cnt, 0, sizeof(cnt));
    for(int i = 1; i <= n; i++){
      cnt[a[i]]++;
    }
    for(int i = 0; i < t; i++){
      if(cnt[i] > 1){
        other++;
      }
      else if(cnt[i] == 1){
        in++;
      }
    }
    for(int l = 1, r = 1, best = -1; l <= n; l++){
      while(r <= n && other > 0){
        if(--cnt[a[r]] == 1){
          other--;
          in++;
        }
        else if(cnt[a[r]] == 0){
          in--;
        }
        r++;
      }
      if(other == 0 && maximize(best, in)){
        L = l;
        R = r;
      }
      if(++cnt[a[l]] == 1){
        in++;
      }
      else if(cnt[a[l]] == 2){
        other++;
      }
    }
    cout << L - 1 << " " << R - 2;
  }
}
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 >> t >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  if(n == t + 1){
    sub1::solve();
  }
  else if(n <= 5000 && false){
    sub35::solve();
  }
  else{
    sub246::solve();
  }
}

Compilation message (stderr)

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

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 22 / 22
• Subtask 6: 24 / 24