Submission #128221

#	Time	Username	Problem	Language	Result	Execution time	Memory
128221		OptxPrime	Minerals (JOI19_minerals)	C++14	40 / 100	948 ms	3440 KiB

minerals

#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 (stderr)

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 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10