fork download
copy 
  1. /// Author : Nguyễn Thái Sơn - K18 - KHMT - UIT
  2. /// Training ICPC 2024
  3.  
  4. #include<bits/stdc++.h>
  5.  
  6. /// #pragma GCC optimize("O3,unroll-loops")
  7. /// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  8.  
  9. #define fi first
  10. #define se second
  11. #define TASK "test"
  12. #define pb push_back
  13. #define EL cout << endl
  14. #define Ti20_ntson int main()
  15. #define in(x) cout << x << endl
  16. #define all(x) (x).begin(),(x).end()
  17. #define getbit(x, i) (((x) >> (i)) & 1)
  18. #define cntbit(x) __builtin_popcount(x)
  19. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  20. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  21. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  22.  
  23. using namespace std;
  24.  
  25. typedef long long ll;
  26. typedef vector<int> vi;
  27. typedef pair<int,int> vii;
  28. typedef unsigned long long ull;
  29. typedef vector<vector<int>> vvi;
  30. int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
  31.  
  32. const int N = 1e6 + 5;
  33. const int oo = INT_MAX;
  34. const int mod = 1e9 + 7;
  35. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  36. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  37.  
  38. int n, a[N], cnt[N];
  39.  
  40. inline void Read_Input() {
  41.     cin >> n;
  42.     FOR(i, 1, n)
  43.         cin >> a[i];
  44. }
  45.  
  46. inline void Solve() {
  47.  
  48.     /// DPT = n ^ 3
  49.  
  50.     /// ko giai duoc voi n = 10^3 -> 10^9
  51.  
  52.     int Ans = n;
  53.  
  54.     /// l - r
  55.  
  56.     /// đoạn
  57.  
  58.  
  59.     int le = 1;
  60.     int ri = n;
  61.  
  62.     /// len co dinh
  63.  
  64.     while (le <= ri) {
  65.         int len = (le + ri) / 2;
  66.  
  67.         /// [1, len] se bi bo di
  68.  
  69.         bool Oke = false;
  70.  
  71.         int num = 0;
  72.         /// số lượng màu xuất hiện  nhiều hơn 1 lần
  73.  
  74.         for (int i = len + 1; i <= n; i++) {
  75.             cnt[a[i]]++;
  76.             if (cnt[a[i]] == 2) num++;
  77.         }
  78.  
  79.  
  80.         if (num == 0) Oke = true;
  81.  
  82.         for (int l = 1, r = l + len - 1; r <= n; l++, r++) {
  83.  
  84.  
  85.             /// [l, r]
  86.  
  87.             /// [l + 1, r + 1]
  88.  
  89.             /// xoa di a[r + 1]
  90.             /// them vao a[l]
  91.  
  92.             cnt[a[l]]++;
  93.             if (cnt[a[l]] == 2) num++;
  94.  
  95.             if (r + 1 <= n) cnt[a[r + 1]]--;
  96.             if (cnt[a[r + 1]] == 1) num--;
  97.  
  98.             if (num == 0) Oke = true;
  99.  
  100. 		}
  101.  
  102. 		if (Oke) Ans = len, ri = len - 1;
  103. 		else le = len + 1;
  104.  
  105. 		for (int i = 1; i <= n; i++)
  106.             cnt[a[i]] = 0;
  107.     }
  108.  
  109.     cout << Ans;
  110. }
  111.  
  112. Ti20_ntson {
  113. //    freopen(TASK".INP","r",stdin);
  114. //    freopen(TASK".OUT","w",stdout);
  115.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  116.     int T = 1;
  117. //    cin >> T;
  118.     while (T -- ) {
  119.         Read_Input();
  120.         Solve();
  121.     }
  122. }
  123.  
  124.  
  125.  
  126.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0wIpps
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!