Submission #1170493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170493		jakubmz2	Minerals (JOI19_minerals)	C++20	100 / 100	28 ms	3844 KiB

minerals

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

const int MAXN = 86002;

int isoff[MAXN];

int rozw(vector<int> lewo, vector<int> prawo, bool c, int prev){
    if(lewo.size() == 0 and prawo.size() == 0) return prev;
    if(lewo.size() == 1 and prawo.size() == 1) { Answer(lewo[0], prawo[0]); return prev; }
    // if(lewo.size() == 2 and prawo.size() == 2){
    //     if(c){
    //         int curr = Query(lewo[0]);
    //         int nowy = Query(prawo[0]);
    //         if(nowy != curr){
    //             Answer(lewo[0], prawo[0]);
    //             Answer(lewo[1], prawo[1]);
    //             return;
    //         }
    //         else{
    //             Answer(lewo[0], prawo[1]);
    //             Answer(lewo[1], prawo[0]);
    //             return;
    //         }
    //     }
    //     else{
    //         int curr = Query(lewo[0]);
    //         int nowy = Query(prawo[0]);
    //         if(nowy == curr){
    //             Answer(lewo[0], prawo[0]);
    //             Answer(lewo[1], prawo[1]);
    //             return;
    //         }
    //         else{
    //             Answer(lewo[0], prawo[1]);
    //             Answer(lewo[1], prawo[0]);
    //             return;
    //         }
    //     }
    // }
    //cerr << lewo.size() << " " << prawo.size() << " " << c << " " << prev << "\n";
    // for(auto u : lewo){
    //     cerr << u << " ";
    // }
    // cout << " lew\n";
    // for(auto u : prawo){
    //     cerr << u << " ";
    // }
    // cerr << " praw\n";
    if(lewo.size() == 0 or prawo.size() == 0) exit(0);
    int mid = lewo.size() / 2;
    vector<int> l1;
    vector<int> l2;
    vector<int> p1;
    vector<int> p2;
    int curr = prev;
    //cerr << mid << " mi\n";
    for(int i = 0; i < prawo.size(); ++i){
        //if(prawo[i] > 44000) cerr << " huhh\n";
    	if(isoff[prawo[i]] == c ^ 1 and l1.size() < mid){
    		l1.push_back(prawo[i]);
    	}
    	else if(isoff[prawo[i]] == c and l2.size() < lewo.size() - mid){
    		l2.push_back(prawo[i]);
    	}
    	else{
    		isoff[prawo[i]] ^= 1;
    		curr = Query(prawo[i]);
    		(l1.size() < l2.size() ? l1.push_back(prawo[i]) : l2.push_back(prawo[i]));
    	}
    }
    for(int i = 0; i < lewo.size(); ++i){
    	if(c == true){
            if(p1.size() == mid){
                p2.push_back(lewo[i]);
                continue;
            }
            else if(p2.size() == lewo.size() - mid){
                p1.push_back(lewo[i]);
                continue;
            }
    		int nowy = Query(lewo[i]);
            isoff[lewo[i]] ^= 1;
    		if(nowy == curr){
    			p2.push_back(lewo[i]);
    		}
    		else{
    			p1.push_back(lewo[i]);
    		}
    		curr = nowy;
    	}
    	else{
            if(p1.size() == mid){
                p2.push_back(lewo[i]);
                continue;
            }
            else if(p2.size() == lewo.size() - mid){
                p1.push_back(lewo[i]);
                continue;
            }
    		int nowy = Query(lewo[i]);
            isoff[lewo[i]] ^= 1;
    		if(nowy != curr){
    			p2.push_back(lewo[i]);
    		}
    		else{
    			p1.push_back(lewo[i]);
    		}
    		curr = nowy;
    	}
    }
    
    int w = rozw(l1, p1, c ^ 1, curr);
    w = rozw(l2, p2, c, w);
    return w;
}

void Solve(int N){
    vector<int> lewo;
    vector<int> prawo;
    int prev = 0;
    for(int i = 1; i <= 2 * N; ++i){
    	if(lewo.size() == N){
    		prawo.push_back(i);
    		continue;
    	}
        int ile = Query(i);
        isoff[i] ^= 1;
        if(ile != prev){
            lewo.push_back(i);
        }
        else{
            prawo.push_back(i);
        }
        prev = ile;
    }
    rozw(lewo, prawo, 1, N);
    return;
}

• 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