oj.uz

Submission #997455

# Submission time Handle Problem Language Result Execution time Memory
997455 2024-06-12T10:52:00 Z DanielPr8 Monochrome Points (JOI20_monochrome) C++14
4 / 100
 2000 ms 456 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
ll n, finale=0;
vll b, w;
ll di(ll a, ll b){
    return min(min(abs(a-b), abs(a-b+n)), abs(a-b-n));
}
bool ins(pll a, pll b){
    if(a.f>a.s)swap(a.f, a.s);
    if(b.f>b.s)swap(b.f, b.s);
    if(a.f>b.f)swap(b, a);
    return (b.f<a.s && a.s<b.s);
}
ll solve(vpl& ans){
    ll ret = 0;
    for(ll i = 0; i < n/2; ++i){
        for(ll j = i+1; j < n/2; ++j){
            if(ins(ans[i], ans[j]))ret++;
        }
    }
    return ret;
}
void en(vll& per){
    vpl nxt;
    for(ll i = 0; i < n/2; ++i){
        nxt.pb({b[i], w[per[i]]});
    }
    finale = max(finale, solve(nxt));
}
void alo(ll m, vb& pas, vll& per){
    if(m==0)en(per);
    for(ll i = 0; i < pas.size(); ++i){
        if(!pas[i]){
            per.pb(i);
            pas[i]=1;
            alo(m-1, pas, per);
            per.pop_back();
            pas[i]=0;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    string s;
    cin >> n >> s;n*=2;
    for(ll i = 0; i < n; ++i){
        if(s[i]=='B')b.pb(i);
        else w.pb(i);
    }
    vb pas(n/2);
    vll per;
    alo(n/2, pas, per);
    cout << finale;
}

Compilation message

monochrome.cpp: In function 'void alo(ll, vb&, vll&)':
monochrome.cpp:44:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(ll i = 0; i < pas.size(); ++i){
      |                   ~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 9 ms 348 KB Output is correct
10 Correct 8 ms 452 KB Output is correct
11 Correct 8 ms 456 KB Output is correct
12 Correct 8 ms 456 KB Output is correct
13 Correct 9 ms 348 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 9 ms 348 KB Output is correct
10 Correct 8 ms 452 KB Output is correct
11 Correct 8 ms 456 KB Output is correct
12 Correct 8 ms 456 KB Output is correct
13 Correct 9 ms 348 KB Output is correct
14 Execution timed out 2067 ms 348 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 9 ms 348 KB Output is correct
10 Correct 8 ms 452 KB Output is correct
11 Correct 8 ms 456 KB Output is correct
12 Correct 8 ms 456 KB Output is correct
13 Correct 9 ms 348 KB Output is correct
14 Execution timed out 2067 ms 348 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 9 ms 348 KB Output is correct
10 Correct 8 ms 452 KB Output is correct
11 Correct 8 ms 456 KB Output is correct
12 Correct 8 ms 456 KB Output is correct
13 Correct 9 ms 348 KB Output is correct
14 Execution timed out 2067 ms 348 KB Time limit exceeded
15 Halted 0 ms 0 KB -