Submission #1283835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283835		dhuyyyy	Robots (APIO13_robots)	C++20	0 / 100	1 ms	332 KiB

robots

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second

using namespace std;

using ii = pair<int,int>;

const int MOD = 1e9+7;
const int N = 1e5+5;

int n, a[N];

namespace subtask5{
    bool check(){
        return n <= 10000;
    }
    const int M = 10005;
    int perm[M];
    struct BIT{
        int n;
        vector <int> bit;
        BIT (int _n = 0) : n(_n){
            bit.assign(n + 2,0);
        }
        void update(int id,int val){
            while (id > 0 ){
                bit[id] += val;
                id -= id & -id;
            }
        }
        int get(int id){
            int res = 0;
            while (id <= n){
                res += bit[id];
                id += id & -id;
            }
            return res;
        }
    };
    void solve(){
        BIT bit(n);
        int total = 0;
        for (int i = 1; i <= n; i++){
            int ok = bit.get(a[i] + 1);
            total += ok;
            perm[i] = ok;
            bit.update(a[i],1);
        }
        int res = total;
        for (int i = 1; i <= n; i++){
            int cur = 0;
            for (int j = i + 1; j <= n; j++){
                res = min(res,total - cur + (j - i - 1 - cur) - perm[j] + (j - i - perm[j]));
                if (a[j] < a[i]){
                    cur++;
                    perm[j]--;
                }
            }
        }
        cout << min(res + 1,total);
    }
};
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    freopen("PSWAP.inp","r",stdin);
    freopen("PSWAP.out","w",stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (subtask5::check()) return subtask5::solve(),0;
    return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:69:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     freopen("PSWAP.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:70:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     freopen("PSWAP.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40