제출 #389155

#제출 시각아이디문제언어결과실행 시간메모리
389155apostoldaniel854곤돌라 (IOI14_gondola)C++14
55 / 100
48 ms4664 KiB
#include <bits/stdc++.h> using namespace std; //#define HOME #ifndef HOME #include "gondola.h" #endif // HOME int valid(int n, int inputSeq[]) { int mn = 0; map <int, int> freq; for (int i = 0; i < n; i++) { if (inputSeq[i] < inputSeq[mn]) mn = i; freq[inputSeq[i]]++; if (freq[inputSeq[i]] > 1) return 0; } rotate (inputSeq, inputSeq + mn, inputSeq + n); int val = inputSeq[0]; for (int i = 0; i < n; i++) { if (inputSeq[i] <= n) { if (val != inputSeq[i]) return 0; } val++; } return 1; } //---------------------- const int max_n = 25e4; int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int mn = 0; for (int i = 0; i < n; i++) { if (gondolaSeq[i] < gondolaSeq[mn]) mn = i; } if (gondolaSeq[mn] <= n) rotate (gondolaSeq, gondolaSeq + (n + mn - gondolaSeq[mn] + 1) % n, gondolaSeq + n); int l = 0; vector <int> pos (1 + max_n); int mx = 0; for (int i = 0; i < n; i++) { pos[gondolaSeq[i]] = i + 1; if (gondolaSeq[i] > gondolaSeq[mx]) mx = i; } int valmax = gondolaSeq[mx]; int cur = mx + 1; for (int i = n + 1; i <= valmax; i++) { if (i == valmax || pos[i] == 0) replacementSeq[l++] = cur, cur = i; else replacementSeq[l++] = pos[i]; } return l; } //---------------------- int countReplacement(int n, int inputSeq[]) { return -3; } #ifdef HOME int gondolaSequence[100001]; int replacementSequence[250001]; int main() { int i, n, tag; int nr; assert(scanf("%d", &tag)==1); assert(scanf("%d", &n)==1); for(i=0;i< n;i++) assert( scanf("%d", &gondolaSequence[i]) ==1); switch (tag){ case 1: case 2: case 3: printf("%d\n", valid(n, gondolaSequence)); break; case 4: case 5: case 6: nr = replacement(n, gondolaSequence, replacementSequence); printf("%d ", nr); if (nr > 0) { for (i=0; i<nr-1; i++) printf("%d ", replacementSequence[i]); printf("%d\n", replacementSequence[nr-1]); } else printf("\n"); break; case 7: case 8: case 9: case 10: printf("%d\n", countReplacement(n, gondolaSequence)); break; } return 0; } #endif // HOME /** 4 2 3 2 **/
#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...