oj.uz

Submission #1113945

# Submission time Handle Problem Language Result Execution time Memory
1113945 2024-11-17T21:42:45 Z mariaclara Alternating Current (BOI18_alternating) C++17
19 / 100
 56 ms 3144 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair 
#define pb push_back
#define fr first 
#define sc second 

int n, m, group[MAXN];
int main() {

    cin >> n >> m;
    vector<pair<pii,int>> v(m);

    for(int i = 0; i < m; i++) {
        cin >> v[i].fr.fr >> v[i].fr.sc;
        if(v[i].fr.fr > v[i].fr.sc) v[i].fr.sc += n;
        v[i].sc = i;
    }

    sort(all(v));
    auto [A,B] = v[0].fr;
    bool possible = 0;

    for(int i = 1; i <= 1; i++) {
        // i é o primeiro elemento do 2° grupo
        group[v[i].sc] = 1;
        auto [C,D] = v[i].fr;

        int B_ = B;
        for(int j = i+1; j < sz(v); j++) {
            if(B_ <= D and B_ - A < n - 1) {
                if(v[j].fr.fr <= B_+1) B_ = max(B_, v[j].fr.sc);
                group[v[j].sc] = 0;
            }
            else {
                if(v[j].fr.fr <= D+1) D = max(D, v[j].fr.sc);
                group[v[j].sc] = 1;
            }
        }
        
        if(B_ - A >= n-1 and D - C >= n-1) {
            possible = 1;
            break;
        }

        group[v[i].sc] = 0;
        if(v[i].fr.fr <= B+1) B = max(B, v[i].fr.sc);
    }

    if(!possible) {
        cout << "impossible\n";
        return 0;
    }

    for(int i = 0; i < m; i++) cout << group[i];
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Incorrect 1 ms 336 KB 'impossible' claimed, but there is a solution
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Incorrect 1 ms 336 KB 'impossible' claimed, but there is a solution
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Incorrect 1 ms 336 KB 'impossible' claimed, but there is a solution
6 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1872 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 18 ms 1104 KB Output is correct
4 Correct 18 ms 1104 KB Output is correct
5 Correct 41 ms 1872 KB Output is correct
6 Correct 41 ms 1860 KB Output is correct
7 Correct 40 ms 2896 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 46 ms 3044 KB Output is correct
11 Correct 35 ms 2044 KB Output is correct
12 Correct 39 ms 2888 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 44 ms 2700 KB Output is correct
16 Correct 18 ms 1608 KB Output is correct
17 Correct 56 ms 3144 KB Output is correct
18 Correct 40 ms 2888 KB Output is correct
19 Correct 4 ms 592 KB Output is correct
20 Correct 44 ms 3132 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Incorrect 1 ms 336 KB 'impossible' claimed, but there is a solution
6 Halted 0 ms 0 KB -