| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 874711 |
2023-11-17T16:35:07 Z |
8pete8 |
Library (JOI18_library) |
C++14 |
|
233 ms |
2184 KB |
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include "library.h"
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<pii,int>
#define vi vector<int>
#define pb push_back
//#define p push
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#pragma GCC optimize ("03,unroll-lopps")
const int mxn=1e3+10,inf=1e9;
deque<int>group[mxn+10];
int pos[mxn+10];
vector<int>q,realans;
vector<pii>adj[mxn+10];
bitset<mxn+10>vis;
void dfs(int cur,int p){
if(group[pos[cur]][0]!=cur)reverse(all(group[pos[cur]]));
for(auto j:group[pos[cur]]){
if(!vis[j])realans.pb(j),vis[j]=true;
}
for(auto i:adj[cur]){
if(i.f==p)continue;
if(i.s<0)realans.pb(-i.s);
dfs(i.f,cur);
}
if(adj[cur].size()!=1)return;
}
int keep,keep2;
void Solve(int n){
int cnt=1;
vector<pii>v;
q.resize(n,0);
group[0].pb(1);
v.pb({1,1});
for(int i=2;i<=n;i++){
bool yes=false;
fill(all(q),0);
for(int j=0;j<=v.size()-1;j++)for(auto k:group[j])q[k-1]=1;
q[i-1]=1;
if(Query(q)-(v.size())==-1)yes=true;
int l=0,r=v.size()-1,ans=inf,ans2=inf;
while(l<=r){
int mid=l+(r-l)/2;
fill(all(q),0);
for(int j=0;j<=mid;j++)for(auto k:group[j])q[k-1]=1;
q[i-1]=1;
int tmp=Query(q);
if(tmp-(mid+1)<=0){
r=mid-1;
if(tmp-(mid+1)==0)ans=min(ans,mid);
}
else l=mid+1;
}
if(ans==inf){
v.pb({i,i});
group[cnt++].pb(i);
}
else{
fill(all(q),0);
q[i-1]=1;
q[v[ans].f-1]=1;
if(Query(q)==1){
keep=v[ans].f;
if(!yes)group[ans].push_front(i),v[ans].f=i;
}
else{
keep=v[ans].s;
if(!yes)group[ans].pb(i),v[ans].s=i;
}
}
if(!yes)continue;
l=ans,r=v.size()-1;
while(l<=r){
fill(all(q),0);
int mid=l+(r-l)/2;
q[i-1]=1;
for(int j=0;j<=mid;j++)for(auto k:group[j])q[k-1]=1;
if(Query(q)-(mid+1)==-1)r=mid-1,ans2=min(ans2,mid);
else l=mid+1;
}
fill(all(q),0);
q[i-1]=1;
q[v[ans2].f-1]=1;
if(Query(q)==1)keep2=v[ans2].f;
else keep2=v[ans2].s;
adj[keep].pb({keep2,-i});
adj[keep2].pb({keep,-i});
}
for(int i=0;i<v.size();i++){
if(v[i].f==v[i].s)continue;
adj[v[i].f].pb({v[i].s,i});
adj[v[i].s].pb({v[i].f,i});
}
for(int i=0;i<cnt;i++)for(auto j:group[i])pos[j]=i;
int st=0;
for(int i=1;i<=n;i++){
if(adj[i].size()==1)st=i;
}
//cout<<st<<'\n';
dfs(st,-1);
//for(auto i:realans)cout<<i<<" ";
Answer(realans);
}
Compilation message
library.cpp:36:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
36 | #pragma GCC optimize ("03,unroll-lopps")
| ^
library.cpp:43:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
43 | void dfs(int cur,int p){
| ^
library.cpp:56:17: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
56 | void Solve(int n){
| ^
library.cpp: In function 'void Solve(int)':
library.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int j=0;j<=v.size()-1;j++)for(auto k:group[j])q[k-1]=1;
| ~^~~~~~~~~~~~
library.cpp:67:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
67 | if(Query(q)-(v.size())==-1)yes=true;
| ~~~~~~~~~~~~~~~~~~~^~~~
library.cpp:116:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int i=0;i<v.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1412 KB |
# of queries: 1848 |
| 2 |
Correct |
19 ms |
1404 KB |
# of queries: 1784 |
| 3 |
Correct |
17 ms |
1928 KB |
# of queries: 1898 |
| 4 |
Correct |
22 ms |
1668 KB |
# of queries: 1834 |
| 5 |
Correct |
23 ms |
1160 KB |
# of queries: 1871 |
| 6 |
Correct |
18 ms |
1672 KB |
# of queries: 1850 |
| 7 |
Correct |
15 ms |
1408 KB |
# of queries: 1851 |
| 8 |
Correct |
20 ms |
1668 KB |
# of queries: 1750 |
| 9 |
Correct |
20 ms |
1664 KB |
# of queries: 1892 |
| 10 |
Correct |
11 ms |
1416 KB |
# of queries: 1147 |
| 11 |
Correct |
1 ms |
1112 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
1148 KB |
# of queries: 3 |
| 13 |
Correct |
1 ms |
1152 KB |
# of queries: 6 |
| 14 |
Correct |
1 ms |
1152 KB |
# of queries: 12 |
| 15 |
Correct |
2 ms |
1148 KB |
# of queries: 73 |
| 16 |
Correct |
2 ms |
1148 KB |
# of queries: 154 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1412 KB |
# of queries: 1848 |
| 2 |
Correct |
19 ms |
1404 KB |
# of queries: 1784 |
| 3 |
Correct |
17 ms |
1928 KB |
# of queries: 1898 |
| 4 |
Correct |
22 ms |
1668 KB |
# of queries: 1834 |
| 5 |
Correct |
23 ms |
1160 KB |
# of queries: 1871 |
| 6 |
Correct |
18 ms |
1672 KB |
# of queries: 1850 |
| 7 |
Correct |
15 ms |
1408 KB |
# of queries: 1851 |
| 8 |
Correct |
20 ms |
1668 KB |
# of queries: 1750 |
| 9 |
Correct |
20 ms |
1664 KB |
# of queries: 1892 |
| 10 |
Correct |
11 ms |
1416 KB |
# of queries: 1147 |
| 11 |
Correct |
1 ms |
1112 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
1148 KB |
# of queries: 3 |
| 13 |
Correct |
1 ms |
1152 KB |
# of queries: 6 |
| 14 |
Correct |
1 ms |
1152 KB |
# of queries: 12 |
| 15 |
Correct |
2 ms |
1148 KB |
# of queries: 73 |
| 16 |
Correct |
2 ms |
1148 KB |
# of queries: 154 |
| 17 |
Correct |
216 ms |
1704 KB |
# of queries: 12406 |
| 18 |
Correct |
233 ms |
1960 KB |
# of queries: 12314 |
| 19 |
Correct |
212 ms |
2172 KB |
# of queries: 12605 |
| 20 |
Correct |
194 ms |
2184 KB |
# of queries: 11777 |
| 21 |
Correct |
171 ms |
1752 KB |
# of queries: 10933 |
| 22 |
Correct |
205 ms |
2184 KB |
# of queries: 12626 |
| 23 |
Correct |
225 ms |
1916 KB |
# of queries: 12452 |
| 24 |
Correct |
81 ms |
1680 KB |
# of queries: 5729 |
| 25 |
Correct |
198 ms |
1756 KB |
# of queries: 12210 |
| 26 |
Correct |
190 ms |
2176 KB |
# of queries: 11437 |
| 27 |
Correct |
76 ms |
1936 KB |
# of queries: 5841 |
| 28 |
Correct |
50 ms |
1164 KB |
# of queries: 2997 |
| 29 |
Correct |
45 ms |
1152 KB |
# of queries: 2994 |
| 30 |
Correct |
58 ms |
1164 KB |
# of queries: 2997 |
