Submission #1169969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169969		bbartek	Minerals (JOI19_minerals)	C++20	40 / 100	15 ms	3116 KiB

minerals

#include <bits/stdc++.h>
#include "minerals.h"

using namespace std;

typedef long long ll;
#define st first
#define nd second
#define pb push_back

const int maxn = 1e5+7;
/*
int para[] = {0,1,3,3,1,2,4,4,2};

set<int> zbior;
int Query(int x) {
    if(zbior.count(x)){
        zbior.erase(x);
    }
    else{
        zbior.insert(x);
    }
    set<int> aktualny;
    for(auto i : zbior){
        aktualny.insert(para[(i)]);
    }
    return aktualny.size();
}

void Answer(int a, int b) {
    //cout<<a<<" "<<b<<"\n";
}
*/

bool zaznaczone[maxn];
vector<pair<int,int>> wyniki;

void rek(vector<int> numery){
    if(numery.size() == 2){
        wyniki.pb({numery[0],numery[1]});
        return;
    }
    vector<int> jeden,dwa;
    int licznik = -1,nowy,stary = 0;
    for(auto i : numery){
        nowy = Query(i);
        licznik++;
        if(nowy == stary){
            zaznaczone[i] = 1;
        }
        if(2*(licznik+1-nowy) >= numery.size()/2){
            stary = nowy;
            for(int j=0;j<=licznik;j++){
                if(zaznaczone[numery[j]])
                    continue;
                nowy = Query(numery[j]);
                if(nowy == stary){
                    jeden.pb(numery[j]);
                }
                else{
                    dwa.pb(numery[j]);
                }
                stary = nowy;
            }
            break;
        }
        stary = nowy;
    }
    for(auto i : numery){
        if(zaznaczone[i]){
            nowy = Query(i);
            zaznaczone[i] = 0;
            jeden.pb(i);
        }
    }
    for(int i=licznik+1;i<numery.size();i++){
        dwa.pb(numery[i]);
    }
    /*
    for(auto i : jeden)
        cout<<i<<" ";
    cout<<"\n";
    for(auto i : dwa)
        cout<<i<<" ";
    cout<<"\n";
    */
    rek(jeden);
    rek(dwa);
    return;
}

void Solve(int n) {   //Query(x) // Answer(a,b)
    vector<int> vect;
    for(int i=1;i<=2*n;i++){
        vect.pb(i);
    }
    rek(vect);

    for(auto i : wyniki){
        Answer(i.st,i.nd);
    }
}

• 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