/ SeriousOJ /

Record Detail

Compile Error 

foo.cc: In function 'int main()':
foo.cc:3:14: error: 'ios' has not been declared
    3 | int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
      |              ^~~
foo.cc:3:43: error: 'cin' was not declared in this scope; did you mean 'std::cin'?
    3 | int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
      |                                           ^~~
      |                                           std::cin
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:146,
                 from foo.cc:1:
/usr/include/c++/13/iostream:62:18: note: 'std::cin' declared here
   62 |   extern istream cin;           ///< Linked to standard input
      |                  ^~~
foo.cc:10:5: error: 'vector' was not declared in this scope
   10 |     vector<int> A(N);
      |     ^~~~~~
foo.cc:10:5: note: suggested alternatives:
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:428:11: note:   'std::vector'
  428 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
/usr/include/c++/13/vector:86:13: note:   'std::pmr::vector'
   86 |       using vector = std::vector<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~
foo.cc:10:12: error: expected primary-expression before 'int'
   10 |     vector<int> A(N);
      |            ^~~
foo.cc:11:40: error: 'A' was not declared in this scope
   11 |     for (int i = 0; i < N; i++) cin >> A[i];
      |                                        ^
foo.cc:14:5: error: 'map' was not declared in this scope
   14 |     map<int,int> freq;
      |     ^~~
foo.cc:14:5: note: suggested alternatives:
In file included from /usr/include/c++/13/map:63,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:152:
/usr/include/c++/13/bits/stl_map.h:102:11: note:   'std::map'
  102 |     class map
      |           ^~~
/usr/include/c++/13/map:80:13: note:   'std::pmr::map'
   80 |       using map
      |             ^~~
foo.cc:14:9: error: expected primary-expression before 'int'
   14 |     map<int,int> freq;
      |         ^~~
foo.cc:15:18: error: 'A' was not declared in this scope
   15 |     for (int x : A) freq[x]++;
      |                  ^
foo.cc:15:21: error: 'freq' was not declared in this scope; did you mean 'free'?
   15 |     for (int x : A) freq[x]++;
      |                     ^~~~
      |                     free
foo.cc:16:12: error: expected primary-expression before 'int'
   16 |     vector<int> vals;
      |            ^~~
foo.cc:17:5: error: 'vals' was not declared in this scope
   17 |     vals.reserve(freq.size());
      |     ^~~~
foo.cc:17:18: error: 'freq' was not declared in this scope; did you mean 'free'?
   17 |     vals.reserve(freq.size());
      |                  ^~~~
      |                  free
foo.cc:22:12: error: expected primary-expression before 'int'
   22 |     vector<int> divisors;
      |            ^~~
foo.cc:25:13: error: 'divisors' was not declared in this scope
   25 |             divisors.push_back(d);
      |             ^~~~~~~~
foo.cc:29:10: error: 'divisors' was not declared in this scope
   29 |     sort(divisors.begin(), divisors.end());
      |          ^~~~~~~~
foo.cc:29:5: error: 'sort' was not declared in this scope; did you mean 'std::sort'?
   29 |     sort(divisors.begin(), divisors.end());
      |     ^~~~
      |     std::sort
In file included from /usr/include/c++/13/algorithm:73,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51:
/usr/include/c++/13/pstl/glue_algorithm_defs.h:296:1: note: 'std::sort' declared here
  296 | sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last);
      | ^~~~
foo.cc:39:9: error: 'unordered_set' was not declared in this scope
   39 |         unordered_set<int> Dset;
      |         ^~~~~~~~~~~~~
foo.cc:39:9: note: suggested alternatives:
In file included from /usr/include/c++/13/unordered_set:41,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:189:
/usr/include/c++/13/bits/unordered_set.h:104:11: note:   'std::unordered_set'
  104 |     class unordered_set
      |           ^~~~~~~~~~~~~
/usr/include/c++/13/unordered_set:58:13: note:   'std::pmr::unordered_set'
   58 |       using unordered_set
      |             ^~~~~~~~~~~~~
foo.cc:39:23: error: expected primary-expression before 'int'
   39 |         unordered_set<int> Dset;
      |                       ^~~
foo.cc:41:9: error: 'Dset' was not declared in this scope
   41 |         Dset.insert(0);
      |         ^~~~
foo.cc:58:34: error: 'min' was not declared in this scope; did you mean 'std::min'?
   58 |                         pairs += min(freq[x], it->second);
      |                                  ^~~
      |                                  std::min
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: 'std::min' declared here
 5785 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
foo.cc:73:5: error: 'cout' was not declared in this scope; did you mean 'std::cout'?
   73 |     cout << answer;
      |     ^~~~
      |     std::cout
/usr/include/c++/13/iostream:63:18: note: 'std::cout' declared here
   63 |   extern ostream cout;          ///< Linked to standard output
      |                  ^~~~

Code

#include <bits/stdc++.h> using namespace std; using ll = long long;

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

int T;
cin >> T;
while (T--) {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    
    // Count frequencies
    map<int,int> freq;
    for (int x : A) freq[x]++;
    vector<int> vals;
    vals.reserve(freq.size());
    for (auto &p : freq) vals.push_back(p.first);
    int V = vals.size();
    
    // Precompute divisors of N
    vector<int> divisors;
    for (int d = 1; d * d <= N; ++d) {
        if (N % d == 0) {
            divisors.push_back(d);
            if (d != N/d) divisors.push_back(N/d);
        }
    }
    sort(divisors.begin(), divisors.end());
    
    int answer = 1; // at least 1 block always possible
    // Try smallest block size m to maximize blocks k = N/m
    for (int m : divisors) {
        if (m < 2) continue;
        int k = N / m;
        bool ok = false;
        
        // Gather possible D values
        unordered_set<int> Dset;
        // include D=0 specially
        Dset.insert(0);
        for (int i = 0; i < V; i++) {
            for (int j = i+1; j < V; j++) {
                Dset.insert(abs(vals[j] - vals[i]));
            }
        }
        
        // Check each D
        for (int D : Dset) {
            int pairs = 0;
            if (D == 0) {
                // count pairs from identical values
                for (auto &p : freq) pairs += p.second / 2;
            } else {
                for (int x : vals) {
                    auto it = freq.find(x + D);
                    if (it != freq.end()) {
                        pairs += min(freq[x], it->second);
                    }
                }
            }
            if (pairs >= k) {
                ok = true;
                break;
            }
        }
        if (ok) {
            answer = k;
            break;
        }
    }
    
    cout << answer;
    if (T) cout << '\n';
}
return 0;

}

Information

Submit By
Type
Submission
Problem
P1162 G. Roy and Maximum Partition
Language
C++17 (G++ 13.2.0)
Submit At
2025-08-03 13:38:57
Judged At
2025-08-03 13:38:57
Judged By
Score
0
Total Time
0ms
Peak Memory
0 Bytes
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. English
  1. © SeriousOJ Forked from © 2005 - 2023 Vijos.org
  2. dc24fca