题意
sol
考虑不合法的情况只有两种:
-
进去了 再次进去
-
没进去 但是出来了
显然可以用未知记录抵消掉
直接开个set维护一下所有未知记录的位置
最优策略一定是最后一次操作位置的后继
同时我们需要记录一下每个人是否在里面
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int m, las[maxn], op[maxn];//las上一次进去的时间 op最后一次操作的位置 set<int> ms; signed main() { //freopen("a.in", "r", stdin); m = read(); for(int i = 1; i <= m; i++) { char c = 'g'; while(c != 'i' && c != 'o' && c != '?') c = getchar(); if(c == 'i') { int x = read(); if(las[x]) {//在里面 auto pos = ms.upper_bound(op[x]); if(pos == ms.end() || (*pos > i)) return printf("%d", i), 0; else ms.erase(pos); } las[x] = 1; op[x] = i; } else if(c == 'o') { int x = read(); if(!las[x]) { auto pos = ms.upper_bound(op[x]); if(pos == ms.end() || (*pos > i)) return printf("%d", i), 0; else ms.erase(pos); } las[x] = 0; op[x] = i; } else ms.insert(i); c = 'g'; } puts("-1"); return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605420.html