# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
164466 | 2019-11-21T01:44:14 Z | dantoh000 | Gondola (IOI14_gondola) | C++14 | 0 ms | 0 KB |
#include "gondola.h" #include <bits/stdc++.h> using namespace std; int valid(int n, int inputSeq[]) { int anchor[n]; unordered_set<int> s; int last = -1; for (int i = 0; i < n; i++){ s.insert(inputSeq[i]); if (inputSeq[i] > n) continue; anchor[i] = (i+n-inputSeq[i])%n; //printf("%d ",anchor[i]); if (last == -1){ last = anchor[i]; } else{ if (last != anchor[i]) return 0; } } if (s.size() != n) return 0; return 1; } int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int l = 0; int maxpos = 1; unordered_map<int,int> pos; for (int i = 0; i < n; i++){ if (gondolaSeq[maxpos-1] < gondolaSeq[i]) maxpos = i+1; } l = gondolaSeq[maxpos-1] - n; int curseq[n]; bool can = false; for (int i = 0; i < n; i++){ pos[gondolaSeq[i]] = i+1; if (gondolaSeq[i] <= n){ can = true; curseq[i] = gondolaSeq[i]; } else curseq[i] = (curseq[(n+i-1)%n]) % n +1 ; } for (int i = 0; i < n; i++){ if (can) curseq[i] = (curseq[(n+i-1)%n]) % n + 1; else curseq[i] = i+1; pos[curseq[i]] = i+1; //printf("%d ",curseq[i]); } for (int i = 0; i < l; i++){ if (pos[i+n+1] == 0) pos[i+n+1] = maxpos; //printf("replacing %d %d\n",i+n+1,pos[i+n+1]); replacementSeq[i] = curseq[pos[i+n+1]-1]; curseq[pos[i+n+1]-1] = i+n+1; pos[replacementSeq[i]] = pos[i+n+1]; } return l; }