2021百度之星初赛第一场1006 毒瘤数据结构题

思路：

维护头两个0的位置，然后模拟。这里记录一种快读模板。

实现：

  1 #include
  2 using namespace std;
  3 namespace fastIO{
  4     #define BUF_SIZE 1000000
  5     #define OUT_SIZE 1000000
  6     #define ll long long
  7     //fread->read
  8     bool IOerror=0;
  9     inline char nc(){
 10         static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
 11         if (p1==pend){
 12             p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
 13             if (pend==p1){IOerror=1;return -1;}
 14             //{printf("IO error!\n");system("pause");for (;;);exit(0);}
 15         }
 16         return *p1++;
 17     }
 18     inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
 19     inline void read(int &x){
 20         bool sign=0; char ch=nc(); x=0;
 21         for (;blank(ch);ch=nc());
 22         if (IOerror)return;
 23         if (ch=='-')sign=1,ch=nc();
 24         for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
 25         if (sign)x=-x;
 26     }
 27     inline void read(ll &x){
 28         bool sign=0; char ch=nc(); x=0;
 29         for (;blank(ch);ch=nc());
 30         if (IOerror)return;
 31         if (ch=='-')sign=1,ch=nc();
 32         for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
 33         if (sign)x=-x;
 34     }
 35     inline void read(double &x){
 36         bool sign=0; char ch=nc(); x=0;
 37         for (;blank(ch);ch=nc());
 38         if (IOerror)return;
 39         if (ch=='-')sign=1,ch=nc();
 40         for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
 41         if (ch=='.'){
 42             double tmp=1; ch=nc();
 43             for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
 44         }
 45         if (sign)x=-x;
 46     }
 47     inline void read(char *s){
 48         char ch=nc();
 49         for (;blank(ch);ch=nc());
 50         if (IOerror)return;
 51         for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
 52         *s=0;
 53     }
 54     inline void read(char &c){
 55         for (c=nc();blank(c);c=nc());
 56         if (IOerror){c=-1;return;}
 57     }
 58     //getchar->read
 59     inline void read1(int &x){
 60         char ch;int bo=0;x=0;
 61         for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
 62         for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
 63         if (bo)x=-x;
 64     }
 65     inline void read1(ll &x){
 66         char ch;int bo=0;x=0;
 67         for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
 68         for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
 69         if (bo)x=-x;
 70     }
 71     inline void read1(double &x){
 72         char ch;int bo=0;x=0;
 73         for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
 74         for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
 75         if (ch=='.'){
 76             double tmp=1;
 77             for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar());
 78         }
 79         if (bo)x=-x;
 80     }
 81     inline void read1(char *s){
 82         char ch=getchar();
 83         for (;blank(ch);ch=getchar());
 84         for (;!blank(ch);ch=getchar())*s++=ch;
 85         *s=0;
 86     }
 87     inline void read1(char &c){for (c=getchar();blank(c);c=getchar());}
 88     //scanf->read
 89     inline void read2(int &x){scanf("%d",&x);}
 90     inline void read2(ll &x){
 91         #ifdef _WIN32
 92             scanf("%I64d",&x);
 93         #else
 94         #ifdef __linux
 95             scanf("%lld",&x);
 96         #else
 97             puts("error:can't recognize the system!");
 98         #endif
 99         #endif
100     }
101     inline void read2(double &x){scanf("%lf",&x);}
102     inline void read2(char *s){scanf("%s",s);}
103     inline void read2(char &c){scanf(" %c",&c);}
104     inline void readln2(char *s){gets(s);}
105     //fwrite->write
106     struct Ostream_fwrite{
107         char *buf,*p1,*pend;
108         Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
109         void out(char ch){
110             if (p1==pend){
111                 fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
112             }
113             *p1++=ch;
114         }
115         void print(int x){
116             static char s[15],*s1;s1=s;
117             if (!x)*s1++='0';if (x<0)out('-'),x=-x;
118             while(x)*s1++=x%10+'0',x/=10;
119             while(s1--!=s)out(*s1);
120         }
121         void println(int x){
122             static char s[15],*s1;s1=s;
123             if (!x)*s1++='0';if (x<0)out('-'),x=-x;
124             while(x)*s1++=x%10+'0',x/=10;
125             while(s1--!=s)out(*s1); out('\n');
126         }
127         void print(ll x){
128             static char s[25],*s1;s1=s;
129             if (!x)*s1++='0';if (x<0)out('-'),x=-x;
130             while(x)*s1++=x%10+'0',x/=10;
131             while(s1--!=s)out(*s1);
132         }
133         void println(ll x){
134             static char s[25],*s1;s1=s;
135             if (!x)*s1++='0';if (x<0)out('-'),x=-x;
136             while(x)*s1++=x%10+'0',x/=10;
137             while(s1--!=s)out(*s1); out('\n');
138         }
139         void print(char *s){while (*s)out(*s++);}
140         void println(char *s){while (*s)out(*s++);out('\n');}
141         void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
142         ~Ostream_fwrite(){flush();}
143     }Ostream;
144     inline void print(int x){Ostream.print(x);}
145     inline void println(int x){Ostream.println(x);}
146     inline void print(char x){Ostream.out(x);}
147     inline void println(char x){Ostream.out(x);Ostream.out('\n');}
148     inline void print(ll x){Ostream.print(x);}
149     inline void println(ll x){Ostream.println(x);}
150     inline void print(char *s){Ostream.print(s);}
151     inline void println(char *s){Ostream.println(s);}
152     inline void println(){Ostream.out('\n');}
153     inline void flush(){Ostream.flush();}
154     //puts->write
155     char Out[OUT_SIZE],*o=Out;
156     inline void print1(int x){
157         static char buf[15];
158         char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
159         while(x)*p1++=x%10+'0',x/=10;
160         while(p1--!=buf)*o++=*p1;
161     }
162     inline void println1(int x){print1(x);*o++='\n';}
163     inline void print1(ll x){
164         static char buf[25];
165         char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
166         while(x)*p1++=x%10+'0',x/=10;
167         while(p1--!=buf)*o++=*p1;
168     }
169     inline void println1(ll x){print1(x);*o++='\n';}
170     inline void print1(char c){*o++=c;}
171     inline void println1(char c){*o++=c;*o++='\n';}
172     inline void print1(char *s){while (*s)*o++=*s++;}
173     inline void println1(char *s){print1(s);*o++='\n';}
174     inline void println1(){*o++='\n';}
175     inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}}
176     struct puts_write{
177         ~puts_write(){flush1();}
178     }_puts;
179     inline void print2(int x){printf("%d",x);}
180     inline void println2(int x){printf("%d\n",x);}
181     inline void print2(char x){printf("%c",x);}
182     inline void println2(char x){printf("%c\n",x);}
183     inline void print2(ll x){
184         #ifdef _WIN32
185             printf("%I64d",x);
186         #else
187         #ifdef __linux
188             printf("%lld",x);
189         #else
190             puts("error:can't recognize the system!");
191         #endif
192         #endif
193     }
194     inline void println2(ll x){print2(x);printf("\n");}
195     inline void println2(){printf("\n");}
196     #undef ll
197     #undef OUT_SIZE
198     #undef BUF_SIZE
199 };
200 int main(){
201     //freopen("in.txt","r",stdin);
202     int n;
203     fastIO::read(n);
204     vector<int>v(n+1,0);
205     int l=1,r=2;
206     for(int i=0;i){
207         int t,x;
208         fastIO::read(t);
209         fastIO::read(x);
210         if(t==1){
211             if(x==l){
212                 l=r;
213                 int i=r+1;
214                 while(i<=n and v[i]==1)i++;
215                 r=i;
216             }
217             else if(x==r){
218                 int i=r+1;
219                 while(i<=n and v[i]==1)i++;
220                 r=i;
221             }
222             v[x]=1;
223         }
224         else{
225             if(x==l){
226                 fastIO::println(r);
227             }
228             else{
229                 fastIO::println(l);
230             }
231         } 
232     }
233     return 0;
234 }