oj.uz

답안 #428668

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
428668 2021-06-15T13:42:08 Z markthitrin 곤돌라 (IOI14_gondola) C++14
75 / 100
 49 ms 4588 KB 
#include "gondola.h"
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
class name {
public:
    int value;
    int base;
    bool operator<(const name& b) const{
        return value > b.value;
    }
    void operator=(const name& b){
        value = b.value;
        base = b.base;
    }
}put_in;
long long mod = 1000000009;
int valid(int n, int inputSeq[])
{
    std::map<int,bool> g;
    int max = 0;
    int find_min = 2000000000;
    int min_pos = 0;
    for(int q = 0 ;q<n;q++){
        if(g[inputSeq[q]])
            return 0;
        g[inputSeq[q]] = true;
        if(find_min > inputSeq[q]){
            find_min = inputSeq[q];
            min_pos = q;
        }
    }
    if(find_min > n)
        return 1;
    int last_pos = min_pos - find_min;
    for(int q = min_pos;q < min_pos + n;q++){
        if(max < inputSeq[q % n] && inputSeq[q % n] <= n){
            if(inputSeq[q % n] - max != q - last_pos)
                return 0;
            max = inputSeq[q % n];
            inputSeq[q % n] = 2000000000;
            last_pos = q;
        }
    }
    for(int q = 0 ;q<n;q++){
        if(inputSeq[q] <= n)
        return 0;
    }
    return 1;
}

//----------------------

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    std::priority_queue<name> g;
    int max = 0;
    for(int q = 0 ;q<n;q++){
        max = std::max(max,gondolaSeq[q]);
    }
    int find_min = 2000000000;
    int min_pos;
    for(int q = 0 ;q<n;q++){
        if(find_min > gondolaSeq[q]){
            find_min = gondolaSeq[q];
            min_pos = q;
        }
    }
    if(find_min > n)
        min_pos = 0;
    else {
        min_pos -= find_min - 1;
        if(min_pos < 0) min_pos += n;
    }
    for(int q = min_pos;q<min_pos + n;q++){
        put_in.value = gondolaSeq[q % n];
        put_in.base = q + 1 - min_pos;
        g.push(put_in);
    }
    int cnt = 0;
    int last_value = n;
    while(!g.empty()){
        put_in = g.top();
        g.pop();
        if(put_in.value <= n)
            continue;
        replacementSeq[cnt++] = put_in.base;
        for(int q = last_value + 1;q<put_in.value;q++){
            replacementSeq[cnt++] = q;
        }
        last_value = put_in.value;
    }
    return cnt;
}

//----------------------
bool valid_g(std::vector<int> inputSeq){
    int n = inputSeq.size();
    std::map<int,bool> g;
    int max = 0;
    int find_min = 2000000000;
    int min_pos = 0;
    for(int q = 0 ;q<n;q++){
        if(g[inputSeq[q]])
            return false;
        g[inputSeq[q]] = true;
        if(find_min > inputSeq[q]){
            find_min = inputSeq[q];
            min_pos = q;
        }
    }
    if(find_min > n)
        return false;
    int last_pos = min_pos - find_min;
    for(int q = min_pos;q < min_pos + n;q++){
        if(max < inputSeq[q % n] && inputSeq[q % n] <= n){
            if(inputSeq[q % n] - max != q - last_pos)
                return false;
            max = inputSeq[q % n];
            inputSeq[q % n] = 2000000000;
            last_pos = q;
        }
    }
    for(int q = 0 ;q<n;q++){
        if(inputSeq[q] <= n)
        return false;
    }
    return true;
}
long long power(long long a,int number){
    if(number == 0)
        return 1;
    if(number == 1)
        return a;
    long long ans = 1;
    if(number% 2)
        ans *= a;
    ans %= mod;
    ans *= power(a,number/2);
    ans%= mod;
    ans*= power(a,number/2);
    ans%=mod;
    return ans;
}
int countReplacement(int n, int inputSeq[])
{
    std::vector<int> copy;
    for(int q = 0 ;q<n;q++){
        copy.push_back(inputSeq[q]);
    }
    if(!valid_g(copy))
        return 0;
    long long ans = 1;
    std::vector<int> h;
    for(int q = 0 ;q<n;q++){
        if(inputSeq[q] > n)
        h.push_back(inputSeq[q]);
    }
    if(h.size() == 0)
        return 1;
    std::sort(h.begin(),h.end());
    int last_value = n;
    int cnt =0;
    while(h.size() != cnt) {
        ans *= power(h.size() - cnt,h[cnt] - last_value - 1);
        ans %= mod;
        last_value = h[cnt];
        cnt++;
    }
    if(h.size() == n){
    while(true){
    
    }
    ans *= (long long)n;
    ans %= mod;
    }
    return int(ans);
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:165:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  165 |     while(h.size() != cnt) {
      |           ~~~~~~~~~^~~~~~
gondola.cpp:171:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  171 |     if(h.size() == n){
      |        ~~~~~~~~~^~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:73:17: warning: 'min_pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |         min_pos -= find_min - 1;
      |         ~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 15 ms 2124 KB Output is correct
7 Correct 11 ms 588 KB Output is correct
8 Correct 40 ms 3916 KB Output is correct
9 Correct 10 ms 1356 KB Output is correct
10 Correct 39 ms 4444 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 17 ms 2124 KB Output is correct
7 Correct 11 ms 604 KB Output is correct
8 Correct 30 ms 3916 KB Output is correct
9 Correct 9 ms 1484 KB Output is correct
10 Correct 46 ms 4476 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 22 ms 1996 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 49 ms 4588 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 18 ms 1732 KB Output is correct
12 Correct 21 ms 1732 KB Output is correct
13 Correct 18 ms 1160 KB Output is correct
14 Correct 18 ms 1732 KB Output is correct
15 Correct 25 ms 2184 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #8
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #9
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 49 ms 4544 KB Output is correct
10 Correct 39 ms 3912 KB Output is correct
11 Correct 14 ms 1552 KB Output is correct
12 Correct 19 ms 1868 KB Output is correct
13 Incorrect 4 ms 588 KB Output isn't correct

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 47 ms 4572 KB Output is correct
10 Correct 40 ms 3756 KB Output is correct
11 Correct 14 ms 1612 KB Output is correct
12 Correct 17 ms 1812 KB Output is correct
13 Incorrect 4 ms 588 KB Output isn't correct
14 Halted 0 ms 0 KB -