oj.uz

Submission #128221

# Submission time Handle Problem Language Result Execution time Memory
128221 2019-07-10T14:32:37 Z OptxPrime Minerals (JOI19_minerals) C++14
40 / 100
 948 ms 3440 KB 
#include <iostream>
#include <cmath>
#include<vector>
#include <algorithm>
#include <utility>
#include<stack>
#include<queue>
#include<map>
#include <fstream>
#include <minerals.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long

#define ans Answer
#define query Query


    bool inside[100010];
    int nn;
    int curr,opencurr,tmp;



    void conquer( vector<int> vec )
    {
       // cout << " ponovo " <<endl;
        int sz = vec.size();
        if( sz==0 ) return;
        if( sz==2 ){
            ans( vec[0], vec[1] );
            return;
        }
       // cout << " ciscenje " <<endl;
        for( int i=1;i<=2*nn;i++ ){
            if( inside[i] ) {
                    query( i ); /// ocistimo prethodno, sporo ciscenje samo za probu
                inside[i]=false;
            }
        }
    //   cout << " gotovo ciscenje " <<endl;
        int gsz=sz/2;
        if( gsz%2==1 ) gsz++;
        int opensz = gsz/2;
        vector<int>vec1,vec2;
        vec1.clear();
        vec2.clear();
         curr=0,opencurr=0;
        for( int i=0;i<sz;i++ ){

        if( vec1.size() >=gsz ){
            vec2.pb( vec[i] ); /// ako si popunio prvu grupu samo dodaj na drugu
        }
        else{
           tmp = query( vec[i] );
           inside[ vec[i] ]=true;
           if( tmp > curr ){ /// dodan novi mineral
                if( opencurr >= opensz ){   ///ako je prva grupa open vec formirana
                    vec2.pb( vec[i] );
                    curr=query( vec[i] ); ///odma ga izbacimo jer nam vise ne treba
                    inside[ vec[i] ]=false;
                }
                else{
                opencurr++;
                vec1.pb( vec[i] );
                curr=tmp;
                }
           }
            else{
                vec1.pb( vec[i] );
                curr=tmp;
            }
        }
    }
        /// zaboravio sam ocistit kveri
    //    for( int i=0;i<vec1.size();i++ ) query[ vec[i] ]; /// ovo valjda ocisti kveri ? skontat fino kako se cisti
        conquer( vec1 );
        conquer( vec2 );
    }


    void Solve(int n)
    {
        nn=n;///globalno n
        vector<int>vec;
        vec.clear();
        for ( int i=1;i<=2*n;i++){
            vec.pb(i);
            inside[i]=false;
        }
        conquer( vec );
    }

Compilation message

minerals.cpp: In function 'void conquer(std::vector<int>)':
minerals.cpp:54:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if( vec1.size() >=gsz ){
             ~~~~~~~~~~~~^~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 12 ms 504 KB Output is correct
3 Correct 35 ms 680 KB Output is correct
4 Correct 120 ms 888 KB Output is correct
5 Correct 393 ms 1344 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 35 ms 680 KB Output is correct
8 Correct 120 ms 888 KB Output is correct
9 Correct 393 ms 1344 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 181 ms 1144 KB Output is correct
12 Correct 392 ms 1528 KB Output is correct
13 Correct 394 ms 1564 KB Output is correct
14 Correct 385 ms 1564 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 35 ms 680 KB Output is correct
8 Correct 120 ms 888 KB Output is correct
9 Correct 393 ms 1344 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 181 ms 1144 KB Output is correct
12 Correct 392 ms 1528 KB Output is correct
13 Correct 394 ms 1564 KB Output is correct
14 Correct 385 ms 1564 KB Output is correct
15 Incorrect 948 ms 3440 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 35 ms 680 KB Output is correct
8 Correct 120 ms 888 KB Output is correct
9 Correct 393 ms 1344 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 181 ms 1144 KB Output is correct
12 Correct 392 ms 1528 KB Output is correct
13 Correct 394 ms 1564 KB Output is correct
14 Correct 385 ms 1564 KB Output is correct
15 Incorrect 948 ms 3440 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 35 ms 680 KB Output is correct
8 Correct 120 ms 888 KB Output is correct
9 Correct 393 ms 1344 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 181 ms 1144 KB Output is correct
12 Correct 392 ms 1528 KB Output is correct
13 Correct 394 ms 1564 KB Output is correct
14 Correct 385 ms 1564 KB Output is correct
15 Incorrect 948 ms 3440 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 35 ms 680 KB Output is correct
8 Correct 120 ms 888 KB Output is correct
9 Correct 393 ms 1344 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 181 ms 1144 KB Output is correct
12 Correct 392 ms 1528 KB Output is correct
13 Correct 394 ms 1564 KB Output is correct
14 Correct 385 ms 1564 KB Output is correct
15 Incorrect 948 ms 3440 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 35 ms 680 KB Output is correct
8 Correct 120 ms 888 KB Output is correct
9 Correct 393 ms 1344 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 181 ms 1144 KB Output is correct
12 Correct 392 ms 1528 KB Output is correct
13 Correct 394 ms 1564 KB Output is correct
14 Correct 385 ms 1564 KB Output is correct
15 Incorrect 948 ms 3440 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 35 ms 680 KB Output is correct
8 Correct 120 ms 888 KB Output is correct
9 Correct 393 ms 1344 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 181 ms 1144 KB Output is correct
12 Correct 392 ms 1528 KB Output is correct
13 Correct 394 ms 1564 KB Output is correct
14 Correct 385 ms 1564 KB Output is correct
15 Incorrect 948 ms 3440 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -