Submission #341079

#	Time	Username	Problem	Language	Result	Execution time	Memory
341079		mohamedsobhi777	Gondola (IOI14_gondola)	C++14	25 / 100	47 ms	4716 KiB

gondola

#include <bits/stdc++.h>

using namespace std;
#define f first
#define s second
#include "gondola.h"

int valid(int n, int inputSeq[])
{
       map<int, int> mp;
       for (int i = 0; i < n; ++i)
              if (mp[inputSeq[i]]++)
                     return 0;
       if (*min_element(inputSeq, inputSeq + n) > n)
              return 1;
       for (int i = 0; i < n; ++i)
              inputSeq[i]--;

       auto check = [&](int i) -> bool {
              bool ret1 = 1;
              for (int j = 1; j < n; ++j)
              {
                     int nxt = (i + j) % n;
                     if (inputSeq[nxt] >= n)
                            continue;
                     if (inputSeq[nxt] != (inputSeq[i] + j) % n)
                            ret1 = 0;
              }
              return ret1;
       };
       for (int i = 0; i < n; ++i)
       {
              if (inputSeq[i] < n)
                     return check(i);
       }
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
       for (int i = 0; i < n; ++i)
              gondolaSeq[i]--;
       vector<int> a(n);
       if (*min_element(gondolaSeq, gondolaSeq + n) >= n)
       {
              iota(a.begin(), a.end(), 0);
       }
       else
       {
              for (int i = 0; i < n; ++i)
              {
                     if (gondolaSeq[i] < n)
                     {
                            for (int j = 0; j < n; ++j)
                            {
                                   a[(i + j) % n] = (gondolaSeq[i] + j) % n;
                            }
                            break;
                     }
              }
       }
       vector<pair<int, int>> v;
       for (int i = 0; i < n; ++i)
       {
              v.push_back({a[i], i});
       }
       sort(v.begin(), v.end());
       int l = 0;
       int nxt = n;

       for (int i = 0; i < n; ++i)
       {
              int j = v[i].s;
              while (a[j] < gondolaSeq[j])
              {
                     a[j] = nxt++;
                     replacementSeq[l++] = v[i].f + 1;
              }
       }
       return l;
}

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

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

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:10:22: warning: control reaches end of non-void function [-Wreturn-type]
   10 |        map<int, int> mp;
      |                      ^~

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