Submission #638388

#	Time	Username	Problem	Language	Result	Execution time	Memory
638388		ggoh	Gondola (IOI14_gondola)	C++14	60 / 100	28 ms	2508 KiB

gondola

#include<gondola.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
 
int valid(int n, int inputSeq[])
{
  vector<int>check(n+1),copy(n);
  for(int i=0;i<n;i++)
  {
    copy[i]=inputSeq[i];
    if(inputSeq[i]<=n)check[inputSeq[i]]=i+1;
  }
  sort(copy.begin(),copy.end());
  for(int i=0;i<n;i++)if(copy[i]==copy[i+1])return 0;
  int c=0,ans=1,pos,t;
  for(int i=1;i<=n;i++)
  {
    if(check[i])
    {
      if(!c)c=i,pos=check[i];
      else
      {
        t=check[i]-pos;
        if(t<=0)t+=n;
        if(t!=i-c)ans=0;
      }
    }
  }
  return ans;
}
 
 
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  vector<int>check(n+1),top(n),ans;
  int c=0,pos;
  for(int i=0;i<n;i++)
  {
    if(gondolaSeq[i]<=n)
    {
      c=gondolaSeq[i];
      pos=i;
    }
  }
  int left=0;
  if(c)
  {
    left=pos-(c-1);
  }
  vector<pair<int,int>>newG;
  for(int i=0;i<n;i++)
  {
    top[i]=i+1;
    newG.push_back({gondolaSeq[i],(i+n-left)%n});
  }
  sort(newG.begin(),newG.end());
  int t=n+1;
  for(auto &k:newG)
  {
    if(top[k.second]==k.first)continue;
    ans.push_back(top[k.second]);
    top[k.second]=t;
    t++;
    while(top[k.second]!=k.first)
    {
      ans.push_back(top[k.second]);
      top[k.second]++;
      t++;
    }
  }
  int sz=(int)ans.size();
  for(int i=0;i<sz;i++)replacementSeq[i]=ans[i];
  return sz;
}
 
 
int countReplacement(int n, int inputSeq[])
{
  if(!valid(n,inputSeq))return 0;
  return 1;
}

• 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: 5 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10