Submission #48758

#	Time	Username	Problem	Language	Result	Execution time	Memory
48758		doowey	Gondola (IOI14_gondola)	C++14	55 / 100	24 ms	4584 KiB

gondola

    #include <bits/stdc++.h>
    #include "gondola.h"
     
    using namespace std;
    typedef pair<int,int> pii;
     
    #define fi first
    #define se second
    #define mp make_pair
     
    const int N = (int)25e4 + 1293;
     
    int valid(int n, int inputSeq[])
    {
      int cnt[N];
      for(int j = 0;j < N;j ++ )
        cnt[j] = 0;
      int rest[n];
      int maz = (int)4e5 + 12345;
      for(int i = 0; i < n;i ++){
        cnt[inputSeq[i]]++;
        if(cnt[inputSeq[i]] >= 2)
          return 0;
        maz = min(maz, inputSeq[i]);
        rest[i] = inputSeq[i];
      }
      if(maz > n)
        return 1;
      int p,j;
      for(int i = 0;i < n;i ++ ){
        if(rest[i] <= n){
          p = rest[i]+1;
          j = i+1;
          j %= N;
          while(p <= n){
            rest[j] = p;
            p++;
            j++;
            j%=n;
          }
          p = 1;
          while(p < rest[i]){
            rest[j] = p;
            j++;
            j %= n;
            p++;
          }
          break;
        }
      }
      for(int i = 0; i < n;i ++){
        if(inputSeq[i] <= n){
          if(rest[i] != inputSeq[i])
            return 0;
        }
      }
      return 1;
    }
     
    //----------------------
     
    int replacement(int n, int gondolas[], int replacementSeq[])
    {
      int rx = 0;
      bool ok = true;
      int start[n];
      for(int i = 0;i < n;i ++){
        if(gondolas[i] > n) 
          ok = false;
        if(gondolas[i] <= n)
          rx = i;
      }
      if(ok)
        return 0;
      int ini;
      if(gondolas[rx] > n)
        start[rx] = 1;
      else
        start[rx] = gondolas[rx];
      int p = start[rx] + 1;
      ini = start[rx];
      rx ++ ;
      while(p <= n){
        rx %= n;
        start[rx] = p;
        rx++;
        p++;
      }
      p = 1;
      rx %= n;
      while(p < ini){
        start[rx] = p;
        p++;
        rx++;
        rx %= n;
      }
      vector<pii> qq;
      for(int i = 0; i < n;i ++)
        if(start[i] < gondolas[i])
          qq.push_back(mp(gondolas[i],i));
      sort(qq.begin(),qq.end());
      int mak;
      int ix;
      int ii = n + 1;
      int sz = 0;
      for(auto x : qq){
        mak = x.fi;
        ix = x.se;
        replacementSeq[sz] = start[ix];
        sz++;
        start[ix] = ii;
        ii++;
        while(start[ix] < mak){
          replacementSeq[sz] = start[ix];
          start[ix] = ii;
          sz++;
          ii++;
        }
        ii = mak + 1;
      }
      return sz;
    }
     
    //----------------------
     
    int countReplacement(int n, int inputSeq[])
    {
      return -3;
    }

• 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