oj.uz

Submission #1027071

# Submission time Handle Problem Language Result Execution time Memory
1027071 2024-07-18T20:24:36 Z MarwenElarbi Gondola (IOI14_gondola) C++17
55 / 100
 1000 ms 9336 KB 
    #include <bits/stdc++.h>
    #include "gondola.h"
    using namespace std;
    #define pb push_back
    #define se second
    #define fi first
    const int nax=5e5+5;
    const int MOD=1e9+9;
    int valid(int n, int inputSeq[])
    {
        vector<pair<int,int>> tab;
        bool test=true;
        set<int> stt;
        for (int i = 0; i < n; ++i)
        {
            stt.insert(inputSeq[i]);
        }
        test&=(stt.size()==n);
        int cnt=-1e9;
        for (int i = 0; i < n; ++i)
        {
            if(inputSeq[i]<=n){
                cnt=(inputSeq[i]-(i+1)+n)%n;
            }
        }
        if(cnt==-1e9) return test;
        for (int i = 0; i < n; ++i)
        {
            if(inputSeq[i]<=n){
                if((inputSeq[i]-(i+1)+n)%n!=cnt) test=false;
            }
        }
        return test;
    }
     
    //----------------------
     
    int replacement(int n, int gondolaSeq[], int replacementSeq[])
    {
        vector<pair<int,int>> tab;
        for (int i = 0; i < n; ++i)
        {
            if(gondolaSeq[i]>n){
                tab.pb({gondolaSeq[i],i+1});
            }
        }
        sort(tab.begin(),tab.end());
        int cnt=n;
        int cur=0;
        for (int i = 0; i < tab.size(); ++i)
        {
            replacementSeq[cur++]=tab[i].se;
            cnt++;
            while(cnt<tab[i].fi){
                replacementSeq[cur++]=cnt++;
            }
        }
        cout <<cur<<endl;
        return cur;   
    }
    
    //----------------------
     
    int countReplacement(int n, int inputSeq[])
    {
        long long cur=1;
        set<int> st;
        if(!valid(n,inputSeq)) return 0;
        for (int i = 0; i < n; ++i)
        {
            st.insert(i);
        }
        for (int i = 0; i < n; ++i)
        {
            if(inputSeq[i]<=n) st.erase(inputSeq[i]);
        }
        if(st.size()==0) return 1;
        set<int> stt;
        for (int i = 0; i < n; ++i)
        {
            if(inputSeq[i]>n) stt.insert(inputSeq[i]);
        }
        int cnt=n;
        if(stt.size()==n) cur=n;
        while(stt.size()){
            //cout <<cnt<<endl;
            for (int i = cnt; i < *stt.begin()-1; ++i)
            {
                cur=(cur*1ll*(int)stt.size())%MOD;
            }
            cnt=*stt.begin();
            stt.erase(*stt.begin());
        }
        return cur;
    }

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:18:26: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |         test&=(stt.size()==n);
      |                ~~~~~~~~~~^~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for (int i = 0; i < tab.size(); ++i)
      |                         ~~^~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:84:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |         if(stt.size()==n) cur=n;
      |            ~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory 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 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 2324 KB Output is correct
7 Correct 20 ms 4180 KB Output is correct
8 Correct 14 ms 4440 KB Output is correct
9 Correct 4 ms 1592 KB Output is correct
10 Correct 23 ms 4956 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 8 ms 2396 KB Output is correct
7 Correct 20 ms 4264 KB Output is correct
8 Correct 14 ms 4444 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct
10 Correct 19 ms 4956 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 9 ms 2396 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 26 ms 5076 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB 잘못된 접근입니다.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 잘못된 접근입니다.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 잘못된 접근입니다.
2 Halted 0 ms 0 KB -

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 440 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory 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 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 444 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 444 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 0 ms 356 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 45 ms 6356 KB Output is correct
10 Correct 39 ms 5044 KB Output is correct
11 Correct 17 ms 2652 KB Output is correct
12 Correct 19 ms 3140 KB Output is correct
13 Correct 4 ms 1116 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory 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 348 KB Output is correct
8 Correct 0 ms 448 KB Output is correct
9 Correct 45 ms 6408 KB Output is correct
10 Correct 36 ms 4944 KB Output is correct
11 Correct 13 ms 2648 KB Output is correct
12 Correct 17 ms 3032 KB Output is correct
13 Correct 5 ms 1112 KB Output is correct
14 Execution timed out 1090 ms 9336 KB Time limit exceeded
15 Halted 0 ms 0 KB -