oj.uz

Submission #582329

# Submission time Handle Problem Language Result Execution time Memory
582329 2022-06-23T16:30:42 Z wdjpng Gondola (IOI14_gondola) C++17
100 / 100
 43 ms 4044 KB 
#include "gondola.h"
#include <bits/stdc++.h>

#define int long long
#define rep(i,n) for(int i = 0; i < ((int) n); i++)
#define all(a) a.begin(), a.end()

using namespace std;
int N =1e5+1;

signed valid(signed n, signed inputSeq[])
{
  int minn = 1e9+1, mini=-1;
  rep(i,n) if((int)inputSeq[i]<minn) {minn=inputSeq[i]; mini=i;}
  vector<int>x(n);
  rep(i,n) x[(i+minn-1+n)%n]=inputSeq[(i+mini)%n];
  rep(i,n) if(x[i]!=i+1&&x[i]<=n) return 0;
  vector<int>doub;
  rep(i,n) if(x[i]>n) doub.push_back(x[i]);
  sort(all(doub));
  rep(i,doub.size()-1) if(doub[i]==doub[i+1]) return 0;
  return 1; 
}

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

signed replacement(signed n, signed gondseq[], signed replacementSeq[])
{
  int minn = 251000, mini=-1;
  rep(i,n) if((int)gondseq[i]<minn) {minn=gondseq[i]; mini=i;}
  vector<int>x(n);
  rep(i,n) x[(i+minn-1+n)%n]=gondseq[(i+mini)%n];

  int cur = 0;
  int maxx = n;
  rep(i,n) maxx=max(maxx,x[i]);
  map<int,int>mp;
  rep(i,n) if(x[i]>n) mp[x[i]]=i;
  auto it = mp.end();
  if(mp.size()) it--;

  vector<int>out;
  vector<int>help(n);
  rep(i,n) help[i]=i+1;
  for(int i = n+1; i <= maxx; i++)
  {
    if(mp.count(i)) {out.push_back(help[mp[i]]); help[mp[i]]=i;}
    else {out.push_back(help[(*it).second]); help[(*it).second]=i;}
  }

  rep(i,maxx-n) replacementSeq[i]=out[i];
  return maxx-n;
}

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

const int MOD = 1e9+9;
int fastpow(int a, int p)
{
  if(p==0) return 1;
  int res = fastpow(a,p/2);
  res=(res*res)%MOD;
  if(p&1) res=(res*a)%MOD;
  return res;
}

signed countReplacement(signed n, signed inputSeq[])
{
  int minn = 1e9+1, mini=-1;
  rep(i,n) if((int)inputSeq[i]<minn) {minn=inputSeq[i]; mini=i;}
  vector<int>x(n);
  rep(i,n) x[(i+minn-1+n)%n]=inputSeq[(i+mini)%n];

  if(!valid(n, inputSeq)) return 0;
  bool notbroke=true;
  rep(i,n) notbroke&=x[i]<=n;
  if(notbroke) return 1;

  bool allbroke = true;
  rep(i,n) allbroke&=x[i]>n;

  vector<int>aid;
  rep(i,n) if(x[i]>n) aid.push_back(x[i]);
  sort(all(aid));

  int res=allbroke?n:1;
  int last = n;
  rep(i, aid.size())
  {
    res=(res*fastpow(aid.size()-i, aid[i]-last-1))%MOD;
    last=aid[i];
  }
  return res;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:34:7: warning: unused variable 'cur' [-Wunused-variable]
   34 |   int cur = 0;
      |       ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 240 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 9 ms 1224 KB Output is correct
8 Correct 11 ms 1100 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 13 ms 1236 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 8 ms 724 KB Output is correct
7 Correct 12 ms 1248 KB Output is correct
8 Correct 10 ms 1108 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 15 ms 1256 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 7 ms 724 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 10 ms 1296 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 468 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 9 ms 1748 KB Output is correct
12 Correct 13 ms 2004 KB Output is correct
13 Correct 28 ms 4044 KB Output is correct
14 Correct 8 ms 1748 KB Output is correct
15 Correct 41 ms 3776 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 22 ms 2284 KB Output is correct
10 Correct 21 ms 2128 KB Output is correct
11 Correct 11 ms 1108 KB Output is correct
12 Correct 8 ms 1236 KB Output is correct
13 Correct 3 ms 468 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 20 ms 2396 KB Output is correct
10 Correct 16 ms 2156 KB Output is correct
11 Correct 7 ms 1108 KB Output is correct
12 Correct 8 ms 1236 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 33 ms 3024 KB Output is correct
15 Correct 43 ms 3244 KB Output is correct
16 Correct 6 ms 980 KB Output is correct
17 Correct 25 ms 2128 KB Output is correct
18 Correct 12 ms 1616 KB Output is correct