oj.uz

Submission #989155

# Submission time Handle Problem Language Result Execution time Memory
989155 2024-05-27T15:48:45 Z khanhphucscratch Minerals (JOI19_minerals) C++14
100 / 100
 284 ms 6148 KB 
#include<bits/stdc++.h>
#include "minerals.h"
using namespace std;
/*int Query(int x)
{
    cout<<"? "<<x<<endl;
    int ans; cin>>ans;
    return ans;
}
void Answer(int a, int b)
{
    cout<<"! "<<a<<" "<<b<<endl;
}*/
set<pair<int, int>> ans;
int dp[43001], place[43001], pre = 0;
bool state[100001];
int changeQuery(int x)
{
    if(x < 0) return 0;
    state[x] ^= 1;
    int cur = Query(x), a = cur - pre;
    pre = cur;
    return a;
}
void calculate(vector<int> a, vector<int> b, int ex, bool full)
{
    if(a.size() == 1){
        ans.insert({a[0], b[0]});
        return;
    }
    int num = place[a.size()];
    for(int i = 0; i < a.size(); i++) if(a[i] == ex){swap(a[i], a[0]); break;}
    /*cout<<"We're solving: "<<full<<" "<<ex<<endl;
    for(int i : a) cout<<i<<" ";
    cout<<endl;
    for(int i : b) cout<<i<<" ";
    cout<<endl;
    cout<<"Optimal: "<<num<<endl;*/
    vector<int> al, ar, bl, br;
    for(int i = 0; i < num; i++){
        al.push_back(a[i]);
        if(ex < 0 || i > 0) changeQuery(a[i]);
    }
    for(int i = num; i < a.size(); i++) ar.push_back(a[i]);
    for(int i = 0; i < b.size()-1; i++){
        if((changeQuery(b[i]) == 0) == full) br.push_back(b[i]);
        else bl.push_back(b[i]);
    }
    int last = b[b.size()-1];
    if(bl.size() == al.size()){
        swap(bl, br); swap(al, ar); full ^= 1;
    }
    bl.push_back(last);
    if(full == 0){ //left are 1
        calculate(bl, al, last, (state[last]^1));
        calculate(ar, br, -1, 0);
    }
    else{ //right are 1
        calculate(bl, al, last, (state[last]^1));
        calculate(ar, br, -1, 1);
    }
}
void Solve(int n)
{
    //Calculate dp
    for(int i = 2; i <= n; i++){
        dp[i] = 1e9;
        for(int j = i/4; 2*j <= i; j++){ //pray
            int val = i+j-1+dp[j]+dp[i-j];
            if(val < dp[i]){dp[i] = val; place[i] = j;}
        }
    }
    vector<int> a, b;
    for(int i = 1; i <= 2*n; i++){
        if(changeQuery(i) == 1) a.push_back(i);
        else b.push_back(i);
    }
    calculate(a, b, -1, 1);
    for(pair<int, int> i : ans) Answer(i.first, i.second);
}

Compilation message

minerals.cpp: In function 'void calculate(std::vector<int>, std::vector<int>, int, bool)':
minerals.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 0; i < a.size(); i++) if(a[i] == ex){swap(a[i], a[0]); break;}
      |                    ~~^~~~~~~~~~
minerals.cpp:44:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = num; i < a.size(); i++) ar.push_back(a[i]);
      |                      ~~^~~~~~~~~~
minerals.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i = 0; i < b.size()-1; i++){
      |                    ~~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 6 ms 900 KB Output is correct
4 Correct 16 ms 1368 KB Output is correct
5 Correct 38 ms 2184 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 6 ms 900 KB Output is correct
8 Correct 16 ms 1368 KB Output is correct
9 Correct 38 ms 2184 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 21 ms 1536 KB Output is correct
12 Correct 39 ms 2144 KB Output is correct
13 Correct 36 ms 2384 KB Output is correct
14 Correct 37 ms 2528 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 6 ms 900 KB Output is correct
8 Correct 16 ms 1368 KB Output is correct
9 Correct 38 ms 2184 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 21 ms 1536 KB Output is correct
12 Correct 39 ms 2144 KB Output is correct
13 Correct 36 ms 2384 KB Output is correct
14 Correct 37 ms 2528 KB Output is correct
15 Correct 206 ms 4828 KB Output is correct
16 Correct 196 ms 4656 KB Output is correct
17 Correct 197 ms 5076 KB Output is correct
18 Correct 239 ms 5420 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 6 ms 900 KB Output is correct
8 Correct 16 ms 1368 KB Output is correct
9 Correct 38 ms 2184 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 21 ms 1536 KB Output is correct
12 Correct 39 ms 2144 KB Output is correct
13 Correct 36 ms 2384 KB Output is correct
14 Correct 37 ms 2528 KB Output is correct
15 Correct 206 ms 4828 KB Output is correct
16 Correct 196 ms 4656 KB Output is correct
17 Correct 197 ms 5076 KB Output is correct
18 Correct 239 ms 5420 KB Output is correct
19 Correct 212 ms 4936 KB Output is correct
20 Correct 204 ms 4956 KB Output is correct
21 Correct 206 ms 5168 KB Output is correct
22 Correct 235 ms 5532 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 6 ms 900 KB Output is correct
8 Correct 16 ms 1368 KB Output is correct
9 Correct 38 ms 2184 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 21 ms 1536 KB Output is correct
12 Correct 39 ms 2144 KB Output is correct
13 Correct 36 ms 2384 KB Output is correct
14 Correct 37 ms 2528 KB Output is correct
15 Correct 206 ms 4828 KB Output is correct
16 Correct 196 ms 4656 KB Output is correct
17 Correct 197 ms 5076 KB Output is correct
18 Correct 239 ms 5420 KB Output is correct
19 Correct 212 ms 4936 KB Output is correct
20 Correct 204 ms 4956 KB Output is correct
21 Correct 206 ms 5168 KB Output is correct
22 Correct 235 ms 5532 KB Output is correct
23 Correct 254 ms 4944 KB Output is correct
24 Correct 261 ms 4928 KB Output is correct
25 Correct 221 ms 5164 KB Output is correct
26 Correct 221 ms 5712 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 6 ms 900 KB Output is correct
8 Correct 16 ms 1368 KB Output is correct
9 Correct 38 ms 2184 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 21 ms 1536 KB Output is correct
12 Correct 39 ms 2144 KB Output is correct
13 Correct 36 ms 2384 KB Output is correct
14 Correct 37 ms 2528 KB Output is correct
15 Correct 206 ms 4828 KB Output is correct
16 Correct 196 ms 4656 KB Output is correct
17 Correct 197 ms 5076 KB Output is correct
18 Correct 239 ms 5420 KB Output is correct
19 Correct 212 ms 4936 KB Output is correct
20 Correct 204 ms 4956 KB Output is correct
21 Correct 206 ms 5168 KB Output is correct
22 Correct 235 ms 5532 KB Output is correct
23 Correct 254 ms 4944 KB Output is correct
24 Correct 261 ms 4928 KB Output is correct
25 Correct 221 ms 5164 KB Output is correct
26 Correct 221 ms 5712 KB Output is correct
27 Correct 233 ms 5080 KB Output is correct
28 Correct 228 ms 5148 KB Output is correct
29 Correct 209 ms 5212 KB Output is correct
30 Correct 219 ms 5904 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 6 ms 900 KB Output is correct
8 Correct 16 ms 1368 KB Output is correct
9 Correct 38 ms 2184 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 21 ms 1536 KB Output is correct
12 Correct 39 ms 2144 KB Output is correct
13 Correct 36 ms 2384 KB Output is correct
14 Correct 37 ms 2528 KB Output is correct
15 Correct 206 ms 4828 KB Output is correct
16 Correct 196 ms 4656 KB Output is correct
17 Correct 197 ms 5076 KB Output is correct
18 Correct 239 ms 5420 KB Output is correct
19 Correct 212 ms 4936 KB Output is correct
20 Correct 204 ms 4956 KB Output is correct
21 Correct 206 ms 5168 KB Output is correct
22 Correct 235 ms 5532 KB Output is correct
23 Correct 254 ms 4944 KB Output is correct
24 Correct 261 ms 4928 KB Output is correct
25 Correct 221 ms 5164 KB Output is correct
26 Correct 221 ms 5712 KB Output is correct
27 Correct 233 ms 5080 KB Output is correct
28 Correct 228 ms 5148 KB Output is correct
29 Correct 209 ms 5212 KB Output is correct
30 Correct 219 ms 5904 KB Output is correct
31 Correct 253 ms 5252 KB Output is correct
32 Correct 231 ms 5280 KB Output is correct
33 Correct 225 ms 5364 KB Output is correct
34 Correct 273 ms 6148 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 6 ms 900 KB Output is correct
8 Correct 16 ms 1368 KB Output is correct
9 Correct 38 ms 2184 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 21 ms 1536 KB Output is correct
12 Correct 39 ms 2144 KB Output is correct
13 Correct 36 ms 2384 KB Output is correct
14 Correct 37 ms 2528 KB Output is correct
15 Correct 206 ms 4828 KB Output is correct
16 Correct 196 ms 4656 KB Output is correct
17 Correct 197 ms 5076 KB Output is correct
18 Correct 239 ms 5420 KB Output is correct
19 Correct 212 ms 4936 KB Output is correct
20 Correct 204 ms 4956 KB Output is correct
21 Correct 206 ms 5168 KB Output is correct
22 Correct 235 ms 5532 KB Output is correct
23 Correct 254 ms 4944 KB Output is correct
24 Correct 261 ms 4928 KB Output is correct
25 Correct 221 ms 5164 KB Output is correct
26 Correct 221 ms 5712 KB Output is correct
27 Correct 233 ms 5080 KB Output is correct
28 Correct 228 ms 5148 KB Output is correct
29 Correct 209 ms 5212 KB Output is correct
30 Correct 219 ms 5904 KB Output is correct
31 Correct 253 ms 5252 KB Output is correct
32 Correct 231 ms 5280 KB Output is correct
33 Correct 225 ms 5364 KB Output is correct
34 Correct 273 ms 6148 KB Output is correct
35 Correct 245 ms 5376 KB Output is correct
36 Correct 284 ms 5372 KB Output is correct
37 Correct 241 ms 5412 KB Output is correct
38 Correct 242 ms 5924 KB Output is correct