Submission #1170405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170405		bbartek	Minerals (JOI19_minerals)	C++20	100 / 100	38 ms	4188 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;
double fi = 1.61;

mt19937 gen(234678);

void rek(vector<int> num1,vector<int> num2,bool parzystosc,bool obrot){
    shuffle(num1.begin(),num1.end(),gen);
    shuffle(num2.begin(),num2.end(),gen);
    if(num1.size() == 1){
        //cout<<num1.size()<<" "<<num2.size()<<" "<<parzystosc<<"\n";
        wyniki.pb({num1[0],num2[0]});
        return;
    }
    vector<int> x1,x2,y1,y2;
    int dlu = num1.size(),nowy,stary;
    int a = (double(dlu) * fi)/(1.0 + fi), b = dlu-a; 
    if(parzystosc == 0){
        for(int i=0;i<b;i++){
            stary = Query(num1[i]);
            x1.pb(num1[i]);
        }   
        for(int i=b;i<dlu;i++){
            y1.pb(num1[i]);
        }
    }
    else{
        for(int i=0;i<a;i++){
            x1.pb(num1[i]);
        }
        for(int i=a;i<dlu;i++){
            stary = Query(num1[i]);
            y1.pb(num1[i]);
        }
    }
    for(int i=0;i<dlu;i++){
        if(x2.size() == x1.size()){
            y2.pb(num2[i]);
            continue;
        }
        if(y2.size() == y1.size()){
            x2.pb(num2[i]);
            continue;
        }
        nowy = Query(num2[i]);
        if(obrot){
            if(nowy == stary){
                y2.pb(num2[i]);
            }
            else{
                x2.pb(num2[i]);
            } 
        }
        else{
            if(nowy == stary){
                x2.pb(num2[i]);
            }
            else{
                y2.pb(num2[i]);
            }
        }
        stary = nowy;
    }
    rek(x1,x2,0,!obrot);
    rek(y1,y2,1,!obrot);

    return;
}

void Solve(int n) {   //Query(x) // Answer(a,b)
    vector<int> vect1,vect2;
    int a=0,b;
    for(int i=1;i<=2*n;i++){
        b = Query(i);
        if(b != a)
            vect1.pb(i);
        else
            vect2.pb(i);

        a = b;
    }
    rek(vect1,vect2,0,1);

    for(int i=0;i<n;i++){
        Answer(wyniki[i].st,wyniki[i].nd);
    }
}
/*
int main(){
    Solve(4);
    return 0;
}
*/

• 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