Submission #806884

#	Time	Username	Problem	Language	Result	Execution time	Memory
806884		oscar1f	Minerals (JOI19_minerals)	C++17	100 / 100	35 ms	3836 KiB

minerals

#include<bits/stdc++.h>
#include "minerals.h"
using namespace std;

int nbCartes;

vector<int> groupeDeb1,groupeDeb2;

void calc(vector<int> gp1,vector<int> gp2,int mis1) {
    /*for (int i:gp1) {
        cout<<i<<" ";
    }
    cout<<"    ";
    for (int i:gp2) {
        cout<<i<<" ";
    }
    cout<<endl;*/
    if (gp1.size()==1) {
        Answer(gp1[0],gp2[0]);
        return;
    }
    int dernRep=0,ans,mid;
    vector<int> nouvDeb1,nouvDeb2,nouvFin1,nouvFin2;
    if (gp1.size()<6) {
        mid=(gp1.size()+mis1)/2;    
    }
    else {
        if (mis1==0) {
            mid=3849*gp1.size()/10000;
        }
        else {
            mid=6167*gp1.size()/10000;
        }
    }
    for (int i=0;i<mid;i++) {
        nouvDeb1.push_back(gp1[i]);
    }
    for (int i=mid;i<(int)gp1.size();i++) {
        nouvFin1.push_back(gp1[i]);
    }

    if (mis1==0) {
        for (int i:nouvDeb1) {
            dernRep=Query(i);
        }
    }
    else {
        for (int i:nouvFin1) {
            dernRep=Query(i);
        }
    }
    for (int i:gp2) {
        if (i!=gp2.back()) {
            ans=Query(i);
            if (ans==dernRep) {
                nouvDeb2.push_back(i);
            }
            else {
                nouvFin2.push_back(i);
            }
            dernRep=ans;
        }
        else {
            if (nouvDeb2.size()==mid) {
                nouvFin2.push_back(i);
            }
            else {
                nouvDeb2.push_back(i);
            }
        }
    }
    calc(nouvDeb1,nouvDeb2,1);
    calc(nouvFin1,nouvFin2,0);
}

void Solve(int N) {
    nbCartes=N;
    int anci=0,ans;
    for (int i=1;i<=2*nbCartes;i++) {
        ans=Query(i);
        if (ans>anci) {
            groupeDeb1.push_back(i);
        }
        else {
            groupeDeb2.push_back(i);
        }
        anci=ans;
    }
    calc(groupeDeb1,groupeDeb2,1);
}

Compilation message (stderr)

minerals.cpp: In function 'void calc(std::vector<int>, std::vector<int>, int)':
minerals.cpp:64:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |             if (nouvDeb2.size()==mid) {
      |                 ~~~~~~~~~~~~~~~^~~~~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10