Submission #1196360

#TimeUsernameProblemLanguageResultExecution timeMemory
1196360dostsGondola (IOI14_gondola)C++20
55 / 100
32 ms4936 KiB
#include "gondola.h" #include <bits/stdc++.h> #pragma GCC target("lzcnt,popcnt") #pragma GCC optimize("O3,unroll-loops") //#define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define all(x) x.begin(),x.end() #define sp << " " << using namespace std; int valid(int n, int inputSeq[]) { map<int,int> saw; vi pos(n+1,-1); for (int i=0;i<n;i++) { if (saw.count(inputSeq[i])) return 0; saw[inputSeq[i]] = 1; if (inputSeq[i] <= n) { pos[inputSeq[i]] = i; } } int frst = -1; int lst = -1,lsty = -1; for (int j = 1;j<=n;j++) { if (pos[j] == -1) continue; if (frst == -1) frst = pos[j]; pos[j] = (pos[j]-frst+n)%n; if (lst != -1 && pos[j]-lst != j-lsty) return 0; lst = pos[j]; lsty = j; } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int cur = n; vi inds(n+1); vi a(n+1); iota(all(a),0ll); int frst = -1; for (int i=1;i<=n;i++) { if (gondolaSeq[i-1] <= n) frst = i; } if (frst != -1) { a[frst] = gondolaSeq[frst-1]; for (int j = frst+1;j<=n;j++) a[j] = a[j-1]%n+1; for (int j = frst-1;j>=1;j--) a[j] = (a[j+1]==1)?n:(a[j+1]-1); } iota(all(inds),0ll); sort(1+all(inds),[&](int x,int y) { return gondolaSeq[x-1] < gondolaSeq[y-1]; }); int ptr = 0; for (int i = 1;i<=n;i++) { int ind = inds[i]; while (gondolaSeq[ind-1] > a[ind]) { replacementSeq[ptr++] = a[ind]; a[ind] = ++cur; } } return ptr; } //---------------------- int countReplacement(int n, int inputSeq[]) { return -3; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...