Submission #248341

#	Time	Username	Problem	Language	Result	Execution time	Memory
248341		tqbfjotld	Minerals (JOI19_minerals)	C++14	100 / 100	648 ms	4724 KiB

minerals

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

int pr = 0;
int memo[43005];
int frac[43005];
vector<pair<int,int> > answers;

int dp(int num){ ///determine what ratio to split a group of num materials
    if (num<=1) return 0;
    if (memo[num]!=-1) return memo[num];
    int mn = 999999999;
    int ans = -1;
    for (int x = max(1,num/3); x<=num/2; x++){
        int opt = dp(x)+dp(num-x)+x+num-1;
        if (opt<mn){
            ans = x;
            mn = opt;
        }
    }
    frac[num] = ans;
    return memo[num] = mn;
}

void rec(vector<int> g1, vector<int> g2, bool on){
    if (g1.size()==1){
        answers.push_back({g1[0],g2[0]});
        return;
    }
    /*printf("g1: ");
    for (int x : g1){
        printf("%d ",x);
    }
    printf("\n");
    printf("g2: ");
    for (int x : g2){
        printf("%d ",x);
    }
    printf("\n");*/
    int spl = frac[g1.size()];
    //printf("split %d\n",spl);
    vector<int> g2l,g2r;
    vector<int> g1l,g1r;
    for (int x = 0; x<g1.size(); x++){
        if (x<spl){
            pr = Query(g1[x]);
            g1l.push_back(g1[x]);
        }
        else
            g1r.push_back(g1[x]);
    }
    int cnt = 0;
    for (int x = 1; x<g2.size(); x++){ ///last one can be inferred from remaining, saves 1 query per recurse
        int t = Query(g2[x]);
        if (t!=pr){
            if (on){
                g2l.push_back(g2[x]);
                cnt++;
            }
            else{
                g2r.push_back(g2[x]);
            }
        }
        else{
            if (on){
                g2r.push_back(g2[x]);
            }
            else{
                g2l.push_back(g2[x]);
                cnt++;
            }
        }
        pr = t;
    }
    if (cnt<spl){
        g2l.push_back(g2[0]);
    }
    else{
        g2r.push_back(g2[0]);
    }
    rec(g1l,g2l,!on);
    rec(g1r,g2r,on);
}


void Solve(int N) {

    vector<int> gr1;
    vector<int> gr2;
    for (int i = 1; i<=2*N; i++){
        int t = Query(i);
        if (t==pr){
            gr2.push_back(i);
        }
        else{
            gr1.push_back(i);
        }
        pr = t;
    }
    memset(memo,-1,sizeof(memo));
    for (int x = 1; x<=N; x++){
        dp(x);
    }
    rec(gr1,gr2,true);

    for (auto x : answers) {
        Answer(x.first,x.second);
    }
}

Compilation message (stderr)

minerals.cpp: In function 'void rec(std::vector<int>, std::vector<int>, bool)':
minerals.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int x = 0; x<g1.size(); x++){
                     ~^~~~~~~~~~
minerals.cpp:54:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int x = 1; x<g2.size(); x++){ ///last one can be inferred from remaining, saves 1 query per recurse
                     ~^~~~~~~~~~

• 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