Submission #48796355

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vi=vector<int>;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//上
#define all(x) (x).begin(), (x).end()
#define GREEN "\033[1;32m"
#define YELLOW "\033[1;33m"
#define PURPLE "\033[1;35m"
#define BLUE "\033[1;36m"
#define trace(...) __f(__LINE__,YELLOW,#__VA_ARGS__, __VA_ARGS__)
#define Trace(color,...) __f(__LINE__,color,#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(int line, const char *color, const char* name, Arg1&& arg1){
cerr << "\033[2;37m(Ln " << line << ")\033[0m " << color << name << ": \033[0;37m" << arg1 << "\033[0m " << endl;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vi=vector<int>;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//上
#define all(x) (x).begin(), (x).end()
#define GREEN "\033[1;32m"
#define YELLOW "\033[1;33m"
#define PURPLE "\033[1;35m"
#define BLUE "\033[1;36m"
#define trace(...) __f(__LINE__,YELLOW,#__VA_ARGS__, __VA_ARGS__)
#define Trace(color,...) __f(__LINE__,color,#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(int line, const char *color, const char* name, Arg1&& arg1){
cerr << "\033[2;37m(Ln " << line << ")\033[0m " << color << name << ": \033[0;37m" << arg1 << "\033[0m " << endl;
}
template <typename Arg1, typename... Args>
void __f(int line, const char *color, const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr << "\033[2;37m(Ln " << line << ")\033[0m " << color;
cerr.write(names, comma - names) << ": \033[0;37m" << arg1 << "\033[0m " << endl;
__f(line,color, comma+1, args...);
}
//IO operators for vectors, pairs, sets, maps and __int128 so I can print just about anything
template <typename T>istream &operator>>(istream &in, vector<T> &v){for (auto &i : v)in >> i;return in;}
template <typename T>ostream &operator<<(ostream &ost, vector<T> v){if(&ost == &cerr){cerr <<"{";int cnt = v.size();for(auto x:v){cerr << x;cnt--;if(cnt) cerr << ", ";}cerr << "}";}else for(auto i:v)ost << i << " ";return ost;}
template <typename T>ostream &operator<<(ostream &ost, set<T> s){if(&ost == &cerr){cerr <<"{";int cnt = s.size();for(auto x:s){cerr << x;cnt--;if(cnt) cerr << ", ";}cerr << "}";}else for(auto i:s)ost << i << " ";return ost;}
template <typename T>ostream &operator<<(ostream &ost, multiset<T> s){if(&ost == &cerr){cerr <<"{";int cnt = s.size();for(auto x:s){cerr << x;cnt--;if(cnt) cerr << ", ";}cerr << "}";}else for(auto i:s)ost << i << " ";return ost;}
template <typename U, typename V>ostream &operator<<(ostream &ost, map<U,V> &m){if(&ost == &cerr){cerr <<"{";int cnt = m.size();for(auto x:m){cerr << x; cnt--;if(cnt) cerr << ", ";}cerr << "}";}else for(auto i:m)ost << i;return ost;}
template <typename U, typename V>istream &operator>>(istream &in, pair<U, V> &p){in>>p.first>>p.second;return in;}
template <typename U, typename V>ostream &operator<<(ostream &ost, pair<U, V> p){if (&ost == &cerr)ost << "{" << p.first << ": " << p.second << "}";else ost << p.first << " " << p.second << " ";return ost;}
ostream &operator<<(ostream &ost, __int128_t x){string output = "";while(x)output += '0'+x%10, x /= 10;reverse(all(output)); ost << output;  return ost;}
istream &operator>>(istream &in, __int128_t &x){x=0;string num;cin >> num;for(char c:num) x *= 10, x += c-'0';return in;}
// istream& operator >> (istream& is, pt& point) {
//   return is >> point.x >> point.y; }
// ostream& operator << (ostream& os, const pt& point) {
//   return os << point.x << ',' << point.y; }
//Variadic IO
template <typename... T>void read(T &...args){((cin >> args), ...);}
template <typename... T>void print(T... args){((cout << args << " "), ...);cout << endl;}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k;
    cin >> n >> k;
    vector<int> v(k);
    vi h;
    FOR(i,0,n) h.push_back(i);
    vi occ(n);
    FOR(i,0,k) {
        int x;
        cin >> x;
        occ[--x]++;
    }

    FOR(i,0,n) if(occ[i] == 0) h.push_back(i);
    sort(h.begin(),h.end());
    int ans = 0;
    if((2*n-k)%2 == 0){
        for(int i = 1; i <h.size();i+=2){
            ans += h[i]-h[i-1];
        }
    }else{
        int r = h.size();
        vector<int> xd((r-1)/2);
        int lol = 0;
        FOR(i,0,(r-1)/2){
            lol += h[i*2+1]-h[i*2];
            xd[i] = lol;
        }
        ans = lol;
        lol = 0;
        int c = 0;
        
        for(int i = (int)h.size()-1; i>= 2; i-=2){
            lol +=h[i]-h[i-1];
            if(i >2){
                ans = min(ans,lol + xd[(i-4)/2]);
            }
        }
        ans = min(ans,lol);

        if(2*n-k == 1) ans = 0;
    }
    cout <<ans<<'\n';
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:67:26: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   67 |         for(int i = 1; i <h.size();i+=2){
      |                        ~~^~~~~~~~~
Main.cpp:80:13: warning: unused variable ‘c’ [-Wunused-variable]
   80 |         int c = 0;
      |             ^

Judge Result