Submission #731278

#	Time	Username	Problem	Language	Result	Execution time	Memory
731278		lucri	Gondola (IOI14_gondola)	C++17	Compilation error	0 ms	0 KiB

gondola

#include <stdio.h>
#include <assert.h>
#include <algorithm>
#include "gondola.h"
#define MOD 1000000009


int poz[100010];
std::unordered_set<int>e;
int valid(int n, int inputSeq[])
{
    for(int i=0;i<n;++i)
    {
        if(e.find(inputSeq[i])!=e.end())
            return 0;
        e.insert(inputSeq[i]);
        if(1<=inputSeq[i]&&inputSeq[i]<=n)
            poz[inputSeq[i]]=i+1;
    }
    int dif=-1;
    for(int i=1;i<=n;++i)
        if(poz[i])
        {
            int val;
            if(i<=poz[i])
                val=poz[i]-i;
            else
                val=poz[i]+n-i;
            if(dif==-1)
                dif=val;
            else if(dif!=val)
                return 0;
        }
    return 1;
}

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

int ago[100010];

int truevalue(int val,int n)
{
  while(val<=0)
    val+=n;
  return val;
}

int goodshift(int n,int gondolaSeq[])
{
  int ls=-1;
  for(int i=0;i<n;++i)
    if(1<=gondolaSeq[i]&&gondolaSeq[i]<=n)
    {
      if(gondolaSeq[i]<=i+1)
        ls=i+1-gondolaSeq[i];
      else
        ls=i+1+n-gondolaSeq[i];
      break;
    }
  if(ls==-1)
  {
    for(int i=0;i<n;++i)
      ago[i+1]=gondolaSeq[i];
    return 0;
  }
  for(int i=0;i<n;++i)
    ago[truevalue(i+1-ls,n)]=gondolaSeq[i];
  return 1;
}

int pozval[250010],valac;

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  goodshift(n,gondolaSeq);
  for(int i=1;i<=n;++i)
    pozval[ago[i]]=i;
  valac=n;
  for(int i=1;i<=n;++i)
    ago[i]=i;
  for(int i=n+1;i<=250000;++i)
  {
    if(pozval[i]!=0)
    {
      while(valac<i)
      {
        replacementSeq[valac-n]=ago[pozval[i]];
        ++valac;
        ago[pozval[i]]=valac;
      }
    }
  }
  return valac-n;
}

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

long long ans=1;

int countReplacement(int n, int inputSeq[])
{
  if(valid(n,inputSeq)==0)
    return 0;
  std::sort(inputSeq,inputSeq+n);
  if(inputSeq[0]>n)
    ans*=n;
  int poz=0;
  while(poz<n&&inputSeq[poz]<=n)
    ++poz;
  for(int i=n+1;i<=inputSeq[n-1];++i)
  {
    if(i==inputSeq[poz])
      ++poz;
    else
    {
      ans*=(n-poz);
      ans%=MOD;
    }
  }
  return ans;
}

Compilation message (stderr)

gondola.cpp:9:6: error: 'unordered_set' in namespace 'std' does not name a template type
    9 | std::unordered_set<int>e;
      |      ^~~~~~~~~~~~~
gondola.cpp:5:1: note: 'std::unordered_set' is defined in header '<unordered_set>'; did you forget to '#include <unordered_set>'?
    4 | #include "gondola.h"
  +++ |+#include <unordered_set>
    5 | #define MOD 1000000009
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:14:12: error: 'e' was not declared in this scope
   14 |         if(e.find(inputSeq[i])!=e.end())
      |            ^
gondola.cpp:16:9: error: 'e' was not declared in this scope
   16 |         e.insert(inputSeq[i]);
      |         ^