제출 #792278

#제출 시각아이디문제언어결과실행 시간메모리
792278MODDI곤돌라 (IOI14_gondola)C++14
20 / 100
9 ms596 KiB
#include "gondola.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair typedef long long ll; typedef pair<long long, long long> pll; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<ll> vl; int valid(int n, int inputSeq[]) { int pos = -1; for(int i = 0; i < n; i++){ if(inputSeq[i] == 1){ pos = i; break; } } bool seq = true; int at = 1, lim = pos; while(pos < n){ if(inputSeq[pos] == at){ pos++; at++; } else{ seq = false; break; } } if(!seq) return 0; pos = 0; while(pos < lim){ if(inputSeq[pos] == at){ pos++; at++; } else{ seq = false; break; } } if(!seq) return 0; return 1; } int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int pos = -1; for(int i = 0; i < n; i++){ if(gondolaSeq[i] >= 1 && gondolaSeq[i] <= n){ pos = i; break; } } if(pos == -1){ vi arr(n); for(int i = 0; i < n; i++) arr[i] = gondolaSeq[i]; sort(arr.begin(), arr.end()); int at = 1, j = 0, rez =0; for(int i = 0; i < n; i++){ while(at < arr[i]){ replacementSeq[j++] = at++; rez++; } at++; } return rez; } else{ vector<pii> arr; for(int i = 0; i < n; i++){ if(gondolaSeq[i] > n){ arr.pb(mp(gondolaSeq[i], i)); } } int at = gondolaSeq[pos]; bool done[n+1]; memset(done, false, sizeof done); while(at <= n){ at++; pos++; pos %= n; } int put = 1, rez = 0, j = 0; int need[n]; for(int i = pos; i < n; i++) need[i] = put++; for(int i = 0; i < pos; i++) need[i] = put++; sort(arr.begin(), arr.end()); map<int,int> seen; for(int i = 0; i < n; i++) seen[gondolaSeq[i]] = i; at = n+1; for(int i = 0; i < (int)arr.size(); i++){ int kade = arr[i].second; while(at < gondolaSeq[kade]){ if(seen[at] != 0){ replacementSeq[j++] = need[seen[at]]; at++; rez++; } else{ replacementSeq[j++] = at++; rez++; } } } replacementSeq[j++] = need[seen[at]]; rez++; return rez; } } //---------------------- 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...