Submission #487277

#	Time	Username	Problem	Language	Result	Execution time	Memory
487277		minhcool	Minerals (JOI19_minerals)	C++17	40 / 100	98 ms	5056 KiB

minerals

#include<minerals.h>
#include<bits/stdc++.h>
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, a[N];
 
set<int> slices;
 
vector<int> le, ri;
 
vector<ii> answer;
 
queue<pair<vector<int>, vector<int>>> que;

int arr[N];

bool ck[N];

int co[N];

int cnt[N], tol = 0;
/*
int Query(int x){
	if(!ck[x]){
		ck[x] = 1;
		if(cnt[co[x]] == 0){
			tol++;
		}
		cnt[co[x]]++;
	}
	else{
		ck[x] = 0;
		if(cnt[co[x]] == 1){
			tol--;
		}
		cnt[co[x]]--;
	}
	return tol;
}

void Answer(int x, int y){
	assert(co[x] == co[y]);
	assert(x != y);
}*/
 
void Solve(int N){
    n = N;
    le.clear();
    ri.clear();
    slices.clear();
    answer.clear();
    int lst = 0;
    for(int i = 1; i <= 2 * n; i++){
        int temp = Query(i);
        slices.insert(i);
        if(lst < temp){
            le.pb(i);
        }
        else{
            ri.pb(i);
        }
        lst = temp;
    }
    for(int i = 1; i <= 2 * n; i++) Query(i);
    slices.clear();
    //vector<int> 
    que.push({le, ri});
    //return;
    while(!que.empty()){
        vector<int> a = que.front().fi, b = que.front().se;
        //cout << a.size() << "\n";
        que.pop();
        //assert(a.size() == b.size());
        if(a.size() != b.size()){
        	cout << "DCM CUOC DOI\n";
        	return;
		}
        if(a.size() == 1){
            answer.pb({a[0], b[0]});
            continue;
        }
        int mid = (a.size() + 1) / 2;
        vector<int> a1, b1, a2, b2;
        for(int i = 0; i < mid; i++){
            Query(a[i]);
            slices.insert(a[i]);
            a1.pb(a[i]);
        }
        for(int i = mid; i < a.size(); i++) a2.pb(a[i]);
        int sum = 0;
        for(int i = 1; i <= 2 * n; i++) sum += (ck[i] == 1);
    	//cout << sum << "\n";
    	//cout << tol << "\n";
        int lst = slices.size();
        for(int i = 0; i < b.size(); i++){
            int temp = Query(b[i]);
            //cout << temp << "\n";
            slices.insert(b[i]);
            if(temp != lst){
                b2.pb(b[i]);
                lst = temp;
            }
            else b1.pb(b[i]);
        }
        for(auto it : slices) Query(it);
        slices.clear();
        if(a1.size() != b1.size() || a2.size() != b2.size()){
        	//cout << a1.size() << " " << b1.size() << " " << a2.size() << " " << b2.size() << "\n";
        	cout << "DAMN\n";
        	return;
		}
        if(a1.size()) que.push({a1, b1});
        if(a2.size()) que.push({a2, b2});
    }
    for(auto it : answer) Answer(it.fi, it.se);
}
/*
void process(){
	int x = 3;
	for(int i = 1; i <= x * 2; i++){
		co[i] = (i + 1) / 2;
	}
	Solve(x);
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}*/

Compilation message (stderr)

minerals.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:102:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int i = mid; i < a.size(); i++) a2.pb(a[i]);
      |                          ~~^~~~~~~~~~
minerals.cpp:108:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for(int i = 0; i < b.size(); i++){
      |                        ~~^~~~~~~~~~

• 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