Submission #1114955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114955		lucascgar	Alternating Current (BOI18_alternating)	C++17	19 / 100	92 ms	9660 KiB

alternating

#include <bits/stdc++.h>

using namespace std;

/*

*/

typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int MAXN = 1e5+10;

vector<int> w[MAXN];
bool ty[MAXN];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout << fixed << setprecision(7);

    int n, m;
    cin >> n >> m;

    int a, b;
    for (int i=0;i<m;i++){
        cin >> a >> b;
        if(b<a) return 0;
        w[a].push_back(i);
        w[b].push_back(i);
    }
    set<int> cr;
    int ps=-1, ng=-1;
    bool valid = 1;
    for (int i=1;i<=n;i++){
        vector<int> rm;
        while (!w[i].empty()){
            int u = w[i].back();
            w[i].pop_back();
            if (!cr.count(u) && ps != u && ng != u){
                cr.insert(u);
            }
            else{
                rm.push_back(u);
            }
        }
        if (cr.size() < (int)(ps==-1)+(ng==-1)){
            valid = 0;
            break;
        }

        if (ps==-1){
            ps = *cr.begin();
            cr.erase(cr.begin());
            ty[ps]=0;
        }
        if (ng==-1){
            ng = *cr.begin();
            cr.erase(cr.begin());
            ty[ng]=1;
        }

        for (auto &u:rm){
            cr.erase(u);
            if (ps==u) ps=-1;
            if (ng==u) ng=-1;
        }
    }

    if (!valid){
        cout << "impossible\n";
        return 0;
    }
    for (int i=0;i<m;i++) cout << (int)ty[i];
    cout << '\n';

    return 0;
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:47:23: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |         if (cr.size() < (int)(ps==-1)+(ng==-1)){
      |             ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 19 / 19
• Subtask 5: 0 / 26