Submission #589463

#	Time	Username	Problem	Language	Result	Execution time	Memory
589463		AlperenT	Gondola (IOI14_gondola)	C++17	55 / 100	27 ms	6052 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"

using namespace std;

int valid(int n, int arr[]){
    int arr2[n];

    copy(arr, arr + n, arr2);

    sort(arr2, arr2 + n);

    if(unique(arr2, arr2 + n) != arr2 + n) return false;

    int mn = *min_element(arr, arr + n);

    if(mn > n) return true;
    else{
        vector<int> v;

        for(int i = 0; i < n; i++){
            if(arr[i] == mn){
                for(int j = i; j < n; j++) v.push_back(arr[j]);
                for(int j = 0; j < i; j++) v.push_back(arr[j]);

                break;
            }
        }

        for(int i = 0; i < n; i++) if(v[i] <= n && v[i] != i + 1) return false;

        return true;
    }
}

//----------------------

int replacement(int n, int arr[], int ansarr[]){
    vector<int> ans, v;

    int mn = *min_element(arr, arr + n);

    if(mn > n) for(int i = 0; i < n; i++) v.push_back(arr[i]);
    else{
        for(int i = 0; i < n; i++){
            if(arr[i] <= n){
                v.assign(n, 0);

                for(int j = 0; j < n; j++) v[(arr[i] - 1 + (j - i) + n + n) % n] = arr[j];

                break;
            }
        }
    }

    map<int, int> mp;

    for(int i = 0; i < n; i++) mp[v[i]] = i;

    vector<int> curarr(n, 0);

    iota(curarr.begin(), curarr.end(), 1);

    int cur = n + 1;

    for(int i = 0; i < n; i++){
        while(curarr[i] != v[i]){
            if(mp.find(cur) == mp.end()){
                ans.push_back(curarr[i]);
                curarr[i] = cur;
            }
            else{
                ans.push_back(curarr[mp[cur]]);
                curarr[mp[cur]] = cur;
            }

            cur++;
        }
    }

    for(int i = 0; i < ans.size(); i++) ansarr[i] = ans[i];

    return ans.size();
}

//----------------------

int countReplacement(int n, int inputSeq[])
{
  return -3;
}

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i = 0; i < ans.size(); i++) ansarr[i] = ans[i];
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10