oj.uz

Submission #989145

# Submission time Handle Problem Language Result Execution time Memory
989145 2024-05-27T15:38:12 Z khanhphucscratch Minerals (JOI19_minerals) C++14
40 / 100
 203 ms 2928 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[43001];
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 0 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 4 ms 484 KB Output is correct
3 Correct 7 ms 796 KB Output is correct
4 Correct 14 ms 1368 KB Output is correct
5 Correct 38 ms 2180 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 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 4 ms 484 KB Output is correct
7 Correct 7 ms 796 KB Output is correct
8 Correct 14 ms 1368 KB Output is correct
9 Correct 38 ms 2180 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 19 ms 1580 KB Output is correct
12 Correct 41 ms 2200 KB Output is correct
13 Correct 35 ms 2164 KB Output is correct
14 Correct 36 ms 2384 KB Output is correct

Subtask #4
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 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 4 ms 484 KB Output is correct
7 Correct 7 ms 796 KB Output is correct
8 Correct 14 ms 1368 KB Output is correct
9 Correct 38 ms 2180 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 19 ms 1580 KB Output is correct
12 Correct 41 ms 2200 KB Output is correct
13 Correct 35 ms 2164 KB Output is correct
14 Correct 36 ms 2384 KB Output is correct
15 Incorrect 203 ms 2928 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #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 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 4 ms 484 KB Output is correct
7 Correct 7 ms 796 KB Output is correct
8 Correct 14 ms 1368 KB Output is correct
9 Correct 38 ms 2180 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 19 ms 1580 KB Output is correct
12 Correct 41 ms 2200 KB Output is correct
13 Correct 35 ms 2164 KB Output is correct
14 Correct 36 ms 2384 KB Output is correct
15 Incorrect 203 ms 2928 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #6
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 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 4 ms 484 KB Output is correct
7 Correct 7 ms 796 KB Output is correct
8 Correct 14 ms 1368 KB Output is correct
9 Correct 38 ms 2180 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 19 ms 1580 KB Output is correct
12 Correct 41 ms 2200 KB Output is correct
13 Correct 35 ms 2164 KB Output is correct
14 Correct 36 ms 2384 KB Output is correct
15 Incorrect 203 ms 2928 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #7
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 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 4 ms 484 KB Output is correct
7 Correct 7 ms 796 KB Output is correct
8 Correct 14 ms 1368 KB Output is correct
9 Correct 38 ms 2180 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 19 ms 1580 KB Output is correct
12 Correct 41 ms 2200 KB Output is correct
13 Correct 35 ms 2164 KB Output is correct
14 Correct 36 ms 2384 KB Output is correct
15 Incorrect 203 ms 2928 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #8
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 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 4 ms 484 KB Output is correct
7 Correct 7 ms 796 KB Output is correct
8 Correct 14 ms 1368 KB Output is correct
9 Correct 38 ms 2180 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 19 ms 1580 KB Output is correct
12 Correct 41 ms 2200 KB Output is correct
13 Correct 35 ms 2164 KB Output is correct
14 Correct 36 ms 2384 KB Output is correct
15 Incorrect 203 ms 2928 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #9
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 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 4 ms 484 KB Output is correct
7 Correct 7 ms 796 KB Output is correct
8 Correct 14 ms 1368 KB Output is correct
9 Correct 38 ms 2180 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 19 ms 1580 KB Output is correct
12 Correct 41 ms 2200 KB Output is correct
13 Correct 35 ms 2164 KB Output is correct
14 Correct 36 ms 2384 KB Output is correct
15 Incorrect 203 ms 2928 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -