# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1025096 | 2024-07-16T15:55:21 Z | nvujica | 곤돌라 (IOI14_gondola) | C++14 | 13 ms | 2520 KB |
#include <bits/stdc++.h> #include "gondola.h" #define ll long long #define fi first #define se second using namespace std; const int maxn = 3e5 + 10, mod = 1e9 + 9; int a[maxn]; int bio[maxn]; vector <pair<int, int> > v; int mul(int x, int y){ return ((ll)x * y) % mod; } int valid(int n, int inputSeq[]){ for(int i = 0; i < n; i++){ a[i] = inputSeq[i] - 1; if(bio[a[i]]) return 0; bio[a[i]] = 1; } for(int i = 0; i < n; i++){ if(a[i] < n){ for(int j = 0; j < n; j++){ if(a[(i + j) % n] < n){ if(a[(i + j) % n] != (a[i] + j) % n) return 0; } } break; } } return 1; } int replacement(int n, int gondolaSeq[], int replacementSeq[]){ for(int i = 0; i < n; i++){ a[i] = gondolaSeq[i]; } for(int i = 0; i < n; i++){ if(a[i] > n) v.push_back({a[i], i}); } for(int i = n - 1; i >= 0; i--){ if(a[i] <= n || !i){ for(int j = 0; j < n; j++){ a[(i + j) % n] = (a[i] - 1 + j) % n + 1; } break; } } // cout << v.size() << endl; sort(v.begin(), v.end()); int p = 0, l = 0; while(p < v.size()){ replacementSeq[l] = a[v[p].se]; // cout << a[v[p].se] << ' '; a[v[p].se] = n + l + 1; l++; if(a[v[p].se] == v[p].fi) p++; } // cout << endl; // cout << l; return l; } int countReplacement(int n, int inputSeq[]){ if(!valid(n, inputSeq)) return 0; for(int i = 0; i < n; i++){ a[i] = inputSeq[i]; } for(int i = 0; i < n; i++){ if(a[i] > n) v.push_back({a[i], i}); } // for(int i = n - 1; i >= 0; i--){ // if(a[i] <= n || !i){ // for(int j = 0; j < n; j++){ // a[(i + j) % n] = (a[i] - 1 + j) % n + 1; // } // break; // } // } // cout << v.size() << endl; // cout << v.size() << endl; // if(v.size() == 0) return 1; sort(v.begin(), v.end()); // for(int i = 0; i < v.size(); i++){ // cout << v[i].fi << ' ' << v[i].se << endl; // } int p = 0, l = n, ans = 1; while(p < v.size()){ l++; if(a[v[p].se] == l){ p++; continue; } ans = mul(ans, v.size() - p); } // cout << endl; // cout << l; if(v.size() == n) ans = mul(ans, n); return ans; } //int main(){ // ios_base::sync_with_stdio(0); // cin.tie(0); // // int n; // cin >> n; // int inputSeq[n]; // for(int i = 0; i < n; i++){ // cin >> inputSeq[i]; // } // cout << countReplacement(n, inputSeq); // // return 0; //}
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 4 ms | 856 KB | Output is correct |
7 | Correct | 6 ms | 1116 KB | Output is correct |
8 | Correct | 6 ms | 1116 KB | Output is correct |
9 | Correct | 2 ms | 600 KB | Output is correct |
10 | Correct | 6 ms | 1372 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 3 ms | 860 KB | Output is correct |
7 | Correct | 6 ms | 952 KB | Output is correct |
8 | Correct | 6 ms | 1116 KB | Output is correct |
9 | Correct | 2 ms | 604 KB | Output is correct |
10 | Correct | 6 ms | 1372 KB | Output is correct |
11 | Correct | 0 ms | 344 KB | Output is correct |
12 | Correct | 0 ms | 344 KB | Output is correct |
13 | Correct | 3 ms | 1372 KB | Output is correct |
14 | Correct | 1 ms | 344 KB | Output is correct |
15 | Correct | 8 ms | 1372 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 6 ms | 860 KB | Output is correct |
12 | Correct | 7 ms | 1112 KB | Output is correct |
13 | Correct | 10 ms | 1752 KB | Output is correct |
14 | Correct | 6 ms | 860 KB | Output is correct |
15 | Correct | 13 ms | 2520 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 344 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 12 ms | 2264 KB | Output is correct |
10 | Correct | 9 ms | 2112 KB | Output is correct |
11 | Correct | 5 ms | 1628 KB | Output is correct |
12 | Correct | 5 ms | 1496 KB | Output is correct |
13 | Correct | 2 ms | 604 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 12 ms | 2384 KB | Output is correct |
10 | Correct | 10 ms | 2008 KB | Output is correct |
11 | Correct | 5 ms | 1628 KB | Output is correct |
12 | Correct | 6 ms | 1496 KB | Output is correct |
13 | Correct | 2 ms | 604 KB | Output is correct |
14 | Runtime error | 8 ms | 1884 KB | Execution killed with signal 11 |
15 | Halted | 0 ms | 0 KB | - |