Submission #487277

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
487277	2021-11-15T02:37:04 Z	minhcool	Minerals (JOI19_minerals)	C++17	40 / 100	98 ms	5056 KB

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

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.0 / 6.0

#	Verdict	Memory	Grader output
1	Correct	200 KB	Output is correct
2	Correct	328 KB	Output is correct
3	Correct	328 KB	Output is correct
4	Correct	328 KB	Output is correct

Subtask #2
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	456 KB	Output is correct
2	Correct	5 ms	584 KB	Output is correct
3	Correct	12 ms	932 KB	Output is correct
4	Correct	29 ms	1420 KB	Output is correct
5	Correct	53 ms	2396 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	3 ms	456 KB	Output is correct
6	Correct	5 ms	584 KB	Output is correct
7	Correct	12 ms	932 KB	Output is correct
8	Correct	29 ms	1420 KB	Output is correct
9	Correct	53 ms	2396 KB	Output is correct
10	Correct	3 ms	456 KB	Output is correct
11	Correct	32 ms	1704 KB	Output is correct
12	Correct	50 ms	2496 KB	Output is correct
13	Correct	46 ms	2548 KB	Output is correct
14	Correct	48 ms	2388 KB	Output is correct

Subtask #4
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	3 ms	456 KB	Output is correct
6	Correct	5 ms	584 KB	Output is correct
7	Correct	12 ms	932 KB	Output is correct
8	Correct	29 ms	1420 KB	Output is correct
9	Correct	53 ms	2396 KB	Output is correct
10	Correct	3 ms	456 KB	Output is correct
11	Correct	32 ms	1704 KB	Output is correct
12	Correct	50 ms	2496 KB	Output is correct
13	Correct	46 ms	2548 KB	Output is correct
14	Correct	48 ms	2388 KB	Output is correct
15	Incorrect	98 ms	5056 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	3 ms	456 KB	Output is correct
6	Correct	5 ms	584 KB	Output is correct
7	Correct	12 ms	932 KB	Output is correct
8	Correct	29 ms	1420 KB	Output is correct
9	Correct	53 ms	2396 KB	Output is correct
10	Correct	3 ms	456 KB	Output is correct
11	Correct	32 ms	1704 KB	Output is correct
12	Correct	50 ms	2496 KB	Output is correct
13	Correct	46 ms	2548 KB	Output is correct
14	Correct	48 ms	2388 KB	Output is correct
15	Incorrect	98 ms	5056 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	3 ms	456 KB	Output is correct
6	Correct	5 ms	584 KB	Output is correct
7	Correct	12 ms	932 KB	Output is correct
8	Correct	29 ms	1420 KB	Output is correct
9	Correct	53 ms	2396 KB	Output is correct
10	Correct	3 ms	456 KB	Output is correct
11	Correct	32 ms	1704 KB	Output is correct
12	Correct	50 ms	2496 KB	Output is correct
13	Correct	46 ms	2548 KB	Output is correct
14	Correct	48 ms	2388 KB	Output is correct
15	Incorrect	98 ms	5056 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	3 ms	456 KB	Output is correct
6	Correct	5 ms	584 KB	Output is correct
7	Correct	12 ms	932 KB	Output is correct
8	Correct	29 ms	1420 KB	Output is correct
9	Correct	53 ms	2396 KB	Output is correct
10	Correct	3 ms	456 KB	Output is correct
11	Correct	32 ms	1704 KB	Output is correct
12	Correct	50 ms	2496 KB	Output is correct
13	Correct	46 ms	2548 KB	Output is correct
14	Correct	48 ms	2388 KB	Output is correct
15	Incorrect	98 ms	5056 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	3 ms	456 KB	Output is correct
6	Correct	5 ms	584 KB	Output is correct
7	Correct	12 ms	932 KB	Output is correct
8	Correct	29 ms	1420 KB	Output is correct
9	Correct	53 ms	2396 KB	Output is correct
10	Correct	3 ms	456 KB	Output is correct
11	Correct	32 ms	1704 KB	Output is correct
12	Correct	50 ms	2496 KB	Output is correct
13	Correct	46 ms	2548 KB	Output is correct
14	Correct	48 ms	2388 KB	Output is correct
15	Incorrect	98 ms	5056 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	3 ms	456 KB	Output is correct
6	Correct	5 ms	584 KB	Output is correct
7	Correct	12 ms	932 KB	Output is correct
8	Correct	29 ms	1420 KB	Output is correct
9	Correct	53 ms	2396 KB	Output is correct
10	Correct	3 ms	456 KB	Output is correct
11	Correct	32 ms	1704 KB	Output is correct
12	Correct	50 ms	2496 KB	Output is correct
13	Correct	46 ms	2548 KB	Output is correct
14	Correct	48 ms	2388 KB	Output is correct
15	Incorrect	98 ms	5056 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-